Erklärung der P- und NP-Klassen durch Lambda-Rechnung

36

In der Einführung und Erläuterung werden P- und NP-Komplexitätsklassen häufig durch Turing-Maschinen gegeben. Eines der Rechenmodelle ist die Lambda-Rechnung. Ich verstehe, dass alle Rechenmodelle gleichwertig sind (und wenn wir irgendetwas in Form von Turing-Maschine einführen können, können wir dies in Form eines Rechenmodells einführen), aber ich habe nie eine Erklärung für die Komplexitätsklassen P und NP durch Lambda-Berechnung gesehen . Kann jemand die Begriffe P und NP der Komplexitätsklassen ohne Turingmaschine und nur mit Lambda als Rechenmodell erklären?

Simplex
quelle
5
Ihre Rechenleistung ist nur für Funktionen über natürliche Zahlen äquivalent, nicht über höhere Typen oder andere Einstellungen.
Kaveh
Vollständigkeit zu prüfen ist manchmal ein eher theoretisches Konzept, um einen Zusammenhang
aufzuzeigen,

Antworten:

38

Turing-Maschinen und λ Kalkül sind nur für die Funktionen NN äquivalent, die sie definieren können.

Vom Standpunkt der rechnerischen Komplexität aus scheinen sie sich unterschiedlich zu verhalten. Der Hauptgrund, warum Leute Turing-Maschinen und nicht λ Kalkül verwenden, um über Komplexität nachzudenken, ist, dass die Verwendung von λ Kalkül naiv zu unrealistischen Komplexitätsmaßen führt, weil Sie Terme (beliebiger Größe) frei in einzelnen β Reduktionsschritten kopieren können, z. B. (λx.xxx)MMMM.Mit anderen Worten, einzelne Reduktionsschritte in λ-Kalkül sind ein mieses Kostenmodell. Im Gegensatz dazu funktionieren einzelne Turing-Maschinen-Reduktionsschritte hervorragend (im Sinne einer guten Vorhersage der tatsächlichen Programmlaufzeit).

Es ist nicht bekannt, wie vollständig die konventionelle Komplexitätstheorie auf Turing-Maschinen-Basis in λ Kalkül wiederhergestellt werden kann. In einem kürzlichen Durchbruch (2014) haben Accattoli und Dal Lago gezeigt, dass große Klassen von Zeitkomplexität wie P , NP und EXP eine natürliche λ Kalkulus-Formulierung erhalten können. Aber kleinere Klassen wie O(n2) oder O(nlogn) kann nicht mit der Accattoli / Dal Lago-Technik präsentiert werden.

Wie konventionelle Raumkomplexität mit λ Kalkül wiederhergestellt werden kann, ist unbekannt.

Martin Berger
quelle
4
Ich habe das Bedürfnis, dies zu klären: Es gibt keine spezielle "Technik", mit der Accattoli und Dal Lago Zeitklassen "präsentieren". Die Darstellung ist die "naive" one: define als die Klasse der Sprachen entscheidbar durch ein λ -Term in f ( n ) β -Reduktion Schritte unter jeder Standard - Reduktionsstrategie ( zB am weitesten links stehenden -äußerste). Accattoli und Dal Lago zeigten unter Verwendung von Techniken aus der linearen Logik, dass es ein Polynom p gibt, so dass λ T I M E ( fλTIME(f(n))λf(n) βp .λTIME(f(n))=TIME(p(f(n))
Damiano Mazza
@DamianoMazza Ja , das ist richtig, was ich meinte ist , dass ich glaube nicht , dass die verwendeten Techniken dieses Ergebnis zeigen , verwendet werden können , um zu zeigen , zB . λTIME(n2)=TIME(n2)
Martin Berger
3
OK, ich verstehe. Eigentlich ist meine Vermutung , dass : Komplexitätsklassen wie T I M E ( n 2 ) oder T I M E ( n log n ) nicht robust sind Man kann nicht erwarten, dass sie bei Änderungen im Rechenmodell stabil sind (dies ist notorisch der Fall, auch wenn wir uns an Turing-Maschinen halten, z. B. Single-Tape vs. Multi-Tape).λTIME(n2)TIME(n2)TIME(n2)TIME(nlogn)
Damiano Mazza
3
@DamianoMazza Ich stimme zu, auch für die Größe des gewählten Alphabets. Ein Algorithmus, der in auf einer n- Bandmaschine ausgeführt wird, kann jedoch in 5 k f 2 ( n ) auf einer 1-Bandmaschine simuliert werden, was eine bescheidene quadratische Vergrößerung darstellt. Was ist die Explosion der aktuellen Übersetzung von Accattoli und Dal Lago? Ich erinnere mich nicht, ob sie es ausdrücklich angeben. f(n)n5kf2(n)
Martin Berger
1
@Jake Der zitierte Artikel befasst sich mit der Beta-Normalisierung (siehe Seite zwei). Ähnliche Ergebnisse waren bereits für andere Formen der Reduktion bekannt, wie die schwache Reduktion (Call-by-Value) - siehe Dal Lago & Martini, 2008 (in diesem Artikel und in cstheory.stackexchange.com/a/397/989 erörtert) ).
Blaisorblade
12

Ich füge einen Teil einer Antwort ein, die ich für eine andere Frage geschrieben habe :

Implicit Computational Complexity aims at characterizing complexity classes by means of dedicated languages. The first results such as Bellantoni-Cook's Theorem were stated in terms of μ-recursive functions, but more recent results use the vocabulary and techniques of λ-calculus. See this Short introduction to Implicit Computational Complexity for more and pointers, or the proceedings of the DICE workshops.

There exist characterizations of (at least) FP by means of λ-calculus.

Bruno
quelle
5

Ich weiß nicht, ob dies einen Teil Ihrer Frage beantwortet, aber es gibt in der Tat alternative Charakterisierungen der Komplexitätsklassen (insb. P und NP) in logischer Hinsicht (Logik 1. Ordnung, Logik 2. Ordnung usw ..).

Zum Beispiel ist die Arbeit von R. Fagin (et al.) In diesem Bereich bemerkenswert (und imo könnte Einsicht in Bezug auf dieP vs NPProblem und Beziehungen mit beschreibender und algorithmischer Komplexität)

Einige weitere Charakterisierungen von rechnerischen Komplexitätsklassen in Bezug auf algorithmische (Kolmogorov-Solomonov) Komplexität sind hier und hier zu finden .

Nikos M.
quelle