Vorstellungen von effizienter Berechnung

11

Ein Turing-Maschinenalgorithmus mit Polynomzeit wird als effizient angesehen, wenn seine Laufzeit im schlimmsten Fall durch eine Polynomfunktion in der Eingabegröße begrenzt ist. Mir ist die starke These von Church-Turing bekannt:

Jedes vernünftige Rechenmodell kann auf Turing-Maschinen effizient simuliert werden

Mir ist jedoch keine solide Theorie zur Analyse der rechnerischen Komplexität von Algorithmen von -calculus bekannt. $\lambda$

Haben wir eine Vorstellung von Recheneffizienz für jedes bekannte Rechenmodell? Gibt es Modelle, die nur für Fragen zur Berechenbarkeit nützlich, für Fragen zur Komplexität der Berechnungen jedoch unbrauchbar sind?

complexity-theory efficiency computation-models Mohammad Al-Turkistany
quelle

9

Soweit ich weiß, sind die Hauptmodelle der Berechenbarkeit λ-Kalkül, Turing-Maschinen und rekursive Funktionen . Mir ist die Situation bezüglich der Komplexität rekursiver Funktionen nicht bekannt, sie können für die Komplexität unbrauchbar sein oder auch nicht.

Es kann als glücklicher Zufall angesehen werden, dass Turing-Maschinen, die nicht so sehr ineffiziente Maschinen sind, auch ein sehr gutes Modell für Komplexität sind. Was die Dinge natürlich gemacht hat, ist, dass es viele Transformationen gibt, an denen polynomielle TMs beteiligt sind. (Universalmaschine, Simulation einer getapten Maschine mit einer 1-getapten Maschine, von einem beliebigen Alphabet zu einem binären, Simulation eines PRAM , ...) und dass Polynome eine Klasse von Funktionen sind, die durch arithmetische Operationen und Kompositionen stabil sind - Das macht sie zu einem guten Kandidaten für die Komplexitätstheorie. $n$

Reine λ-Rechnung war an sich für die Komplexität nutzlos. Es kam jedoch ein einfaches Typsystem ins Spiel, das auf sehr einfache Weise Kündigungsgarantien für einige λ-Terme ermöglichte. Dann erlaubten einige andere Systeme (Systeme T , F , ..) eine große Ausdruckskraft, während die Terminierung beibehalten wurde.

Effizienz oder Komplexität sind eine Verfeinerung der Terminierung und der Typen, die eng mit der Logik verbunden sind. Später kamen leichte lineare Logiken, die mehrere Komplexitätsklassen charakterisieren. ( Elementary , P und einige Variationen für PSPACE und andere). Die Forschung auf diesem Gebiet ist sehr aktiv und nicht auf diese Komplexitätsklassen beschränkt, und sie ist nicht einmal auf den λ-Kalkül beschränkt.

tl; dr: λ-Kalkül war nützlich für die Berechenbarkeits-, Terminierungs- und Komplexitätstheorie.

Kredit zu geben, wo Kredit fällig ist Turing-Maschinen sind eine gute und einstimmige Methode, um die Komplexität zu definieren. Dies gilt jedoch nur für lose Grenzen wie "Polynom", nicht für enge Grenzen, für die PRAM-ähnliche Modelle besser geeignet sind.

jmad
quelle

Warum führen wir dann die meisten unserer Laufzeitanalysen mit RAM-ähnlichen Modellen durch?

Raphael

Die Realität hat grundlegende Speicheroperationen in (ich würde argumentieren ), daher sind RAM-ähnliche Modelle viel besser für enge Grenzen wie . Sie haben also Recht: Turing-Maschinen sind großartig, wenn die Transformation von PRAM Ihre Bindung nicht wesentlich beeinflusst. (Zum Beispiel, wenn Sie beweisen, dass Ihr Problem in P oder in L / NL liegt)

O (1)

$O(1)$

O (\log | m e m o r y |)

$O(\log |memory|)$

n^{\log_{2} 7}

$n^{\log_27}$

jmad

@ Raphael: Du hast auf meinen letzten Satz reagiert, oder?

jmad

Ja, das habe ich getan (um des unerfahrenen Lesers willen).

Raphael

1

In Bezug auf die zeitliche Komplexität denke ich, dass dies für die Lambda-Rechnung schwierig ist. Der Grund ist, dass der Einheitsberechnungsschritt in der Lambda-Berechnung Reduktion ( Wikipedia-Eintrag ) ist: Alle Ausdrücke, unabhängig davon von ihrer Länge würde Rechenzeitschritt unter diesem Modell dauern . $\beta$

(λ x . t e r m) v \to t e r m [x := v]

$(\lambda x.{\rm term})v \to {\rm term}[x := v]$

1

$1$

quelle

Sie können die Reduzierung in Bezug auf die Anzahl oder Größe der Redexes kosten. Dies wurde in der Tat ausführlich untersucht (suchen Sie beispielsweise nach Referenzen zur optimalen Reduktion).

β

$\beta$

Gilles 'SO - hör auf böse zu sein'

@ Gilles: Da wir nicht wissen, wie hoch die tatsächlichen (einheitlichen) Kosten für die Implementierung einer optimalen Reduzierung sind, ist Ihre Bemerkung nicht wirklich relevant. Derzeit liefern diese Studien nur eine Verfeinerung des in dieser Antwort genannten Problems.

Stéphane Gimenez

1

Über die Einbeziehung des λ-Kalküls in das Standardkomplexitätsmodell finden Sie hier die Zusammenfassung einiger (sehr) neuer Forschungen zu diesem Thema. Es gibt eine Antwort auf diese Frage für eine eingeschränkte Form der β-Reduktion. Grundsätzlich ähnelt die Komplexität des Standardkostenmodells der Zählung von β-Reduktionsschritten, wenn sie auf die Kopfreduktion beschränkt ist (einschließlich Call-by-Name- und Call-by-Value-Strategien).

Zur Invarianz des Einheitskostenmodells für die Kopfreduktion von Beniamino Accattoli und Ugo Dal Lago. (WST2012, Link zum Verfahren )

Der λ-Kalkül ist ein weithin akzeptiertes Rechenmodell für Funktionsprogramme höherer Ordnung, es gibt jedoch kein direktes und allgemein akzeptiertes Kostenmodell dafür. Infolgedessen wird die rechnerische Schwierigkeit, λ-Terme auf ihre normale Form zu reduzieren, typischerweise durch Überlegungen zu konkreten Implementierungsalgorithmen untersucht. Hier zeigen wir, dass das Einheitskostenmodell tatsächlich unveränderlich ist, wenn die Kopfreduktion die zugrunde liegende Dynamik ist. Dies verbessert bekannte Ergebnisse, die sich nur mit einer schwachen Reduzierung (Call-by-Value oder Call-by-Name) befassen. Die Invarianz wird durch einen linearen Kalkül expliziter Substitutionen bewiesen, der es ermöglicht, jeden Kopfreduktionsschritt im λ-Kalkül in elementarere Substitutionsschritte zu zerlegen, wodurch die Kombinatorik der Kopfreduktion leichter zu überlegen ist.

Stéphane Gimenez
quelle

Das OP fragte nach Modellen, die keine Komplexitätsanalyse zulassen. -calculus diente nur als Motivation.

λ

$\lambda$

Raphael

Vorstellungen von effizienter Berechnung

Antworten: