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

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?

cc.complexity-theory complexity-classes turing-machines lambda-calculus Simplex
quelle

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:

Turing-Maschinen und $\lambda$ Kalkül sind nur für die Funktionen $\mathbb{N} \rightarrow \mathbb{N}$ ä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 $\lambda$ Kalkül verwenden, um über Komplexität nachzudenken, ist, dass die Verwendung von $\lambda$ Kalkül naiv zu unrealistischen Komplexitätsmaßen führt, weil Sie Terme (beliebiger Größe) frei in einzelnen $\beta$ Reduktionsschritten kopieren können, z. B. $(\lambda x.xxx)M \rightarrow MMM.$ Mit anderen Worten, einzelne Reduktionsschritte in $\lambda$ -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 $\lambda$ 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 $\lambda$ Kalkulus-Formulierung erhalten können. Aber kleinere Klassen wie $O(n^2)$ oder $O(n \, log\, n)$ kann nicht mit der Accattoli / Dal Lago-Technik präsentiert werden.

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

Martin Berger
quelle

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

-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

so dass

λ T I M E (f (n))

$\lambda TIME(f(n))$

λ

$\lambda$

f (n)

$f(n)$

β

$\beta$

p

$p$

λ T I M E (f (n)) = T I M E (p (f (n))

$\lambda 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

λ T I M E (n^{2}) = T I M E (n^{2})

$\lambda TIME(n^2) = TIME(n^2)$

Martin Berger

OK, ich verstehe. Eigentlich ist meine Vermutung , dass

: Komplexitätsklassen wie

oder

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).

λ T I M E (n^{2}) \neq T I M E (n^{2})

$\lambda TIME(n^2)\neq TIME(n^2)$

T I M E (n^{2})

$TIME(n^2)$

T I M E (n \log n)

$TIME(n\log n)$

Damiano Mazza

@DamianoMazza Ich stimme zu, auch für die Größe des gewählten Alphabets. Ein Algorithmus, der in

auf einer

Bandmaschine ausgeführt wird, kann jedoch in

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)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger

@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

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 $\mu$ -recursive functions, but more recent results use the vocabulary and techniques of $\lambda$ -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) $\mathsf{FP}$ by means of $\lambda$ -calculus.

Bruno
quelle

Ich weiß nicht, ob dies einen Teil Ihrer Frage beantwortet, aber es gibt in der Tat alternative Charakterisierungen der Komplexitätsklassen (insb. $\mathbb{P}$ und $\mathbb{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 die $\mathbb{P}$ vs $\mathbb{NP}$ Problem 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