Sind Laufzeitgrenzen in P bestimmbar? (Antwort: nein)

64

Die Frage ist, ob die folgende Frage entscheidbar ist:

Problem   Ist die Laufzeit von Anbetracht einer Ganzzahl und Turing-Maschine versprochen wurde, dass sie in P ist, in Bezug auf die Eingabelänge ?M M O ( n k ) nkMM O(nk)n

Eine knappe Antwort von "Ja", "Nein" oder "Offen" ist akzeptabel (mit Referenzen, Beweisskizze oder einer Überprüfung des gegenwärtigen Wissens), aber auch umfassendere Antworten sind sehr willkommen.

Antworten

Emanuele Viola hat den Beweis erbracht, dass die Frage unentscheidbar ist (siehe unten).

Hintergrund

Für mich ist diese Frage natürlich beim Parsen von Luca Tevisans Antwort auf die Frage entstanden. Benötigen Laufzeiten für P EXP-Ressourcen für die Obergrenze? … Sind konkrete Beispiele bekannt?

Die Frage bezieht sich auch auf eine MathOverflow-Frage: Was sind die attraktivsten Turing-Unentscheidbarkeitsprobleme in der Mathematik? in einer Variation, in der das Wort "Mathematik" in "Technik" geändert wird, in Anerkennung, dass die Laufzeitschätzung ein allgegenwärtiges technisches Problem ist, das (zum Beispiel) mit der Steuerungstheorie und dem Schaltungsdesign verbunden ist.

Das allgemeine Ziel bei der Beantwortung dieser Frage besteht daher darin, ein besseres Verständnis dafür zu erlangen, welche praktischen Aspekte der Laufzeitschätzung in der Komplexitätsklasse P durchführbar sind (dh Rechenressourcen für die Schätzung in P erfordern) und welche nicht (dh) durchführbar sind. erfordern Rechenressourcen in EXP zu schätzen), im Gegensatz zu formal unentscheidbar.

--- editieren (nach Beantwortung) ---

Ich habe Violas Theorem zu MathOverflows Community-Wiki "Attraktive Turing-Unentscheidbare Probleme" hinzugefügt . Es ist der erste Beitrag des Wikis, der der Komplexitätsklasse P zugeordnet ist. Dies zeugt von der Neuheit, Natürlichkeit und dem breiten Anwendungsbereich von Violas Theorem (und meiner Meinung nach auch von seiner Schönheit).

--- editieren (nach Beantwortung) ---

Juris Hartmanis 'Monografie Machbare Berechnungen und nachweisbare Komplexitätseigenschaften (1978) decken einen Großteil des Materials ab, das Emanuele Violas Beweis liefert.

John Sidles
quelle
Auf Fragen, die im Weblog von Lance Fortnow und Bill GASARCH zum Thema "75 Jahre Informatik" gestellt wurden, habe ich mir oft gewünscht, Turing hätte nüchtern gefragt: "Was sind die überprüfbaren Prozesse, die beim Rechnen eines Computers durchgeführt werden können? Zahl? "... anstatt Turing die schicksalhaft schwierigere Frage zu stellen:" Welche möglichen Prozesse können beim Berechnen einer Zahl ausgeführt werden? " in NP, wessen Mitgliedschaft in P ist unentscheidbar? "Dies soll zeigen, dass ich immer noch darüber nachdenke! :)
John Sidles
2
Obwohl ich Emanuele Violas Beweis klarer finde, wurde eine sehr ähnliche Frage auf Mathoverflow gestellt und beantwortet: mathoverflow.net/questions/28056/…
Alex ten Brink
Einige der Antworten und Ideen in diesem Thread erwiesen sich als relevant für einen Aufsatz / eine Fragensammlung, die Dick Lipton in seinem Weblog Godels Lost Letter veröffentlicht hat . dieser Aufsatz / Fragensatz lautet "Getting On Base With P = NP". URL: rjlipton.wordpress.com/2011/07/04/getting-on-base-with-pnp
John Sidles
Obwohl die Grenzen in P unentscheidbar sind, hindert es einen nicht daran, es zu versuchen (indem man sich weiter einschränkt). Ein Beispiel in dieser theoretischen Antwort
Artem Kaznatcheev
1
Diese Frage inspirierte den folgenden Artikel: arxiv.org/abs/1307.3648
David G

Antworten:

83

Das Problem ist nicht zu entscheiden. Insbesondere können Sie das Problem des Anhaltens wie folgt reduzieren. Konstruieren Sie für eine Instanz des Halteproblems eine neue Maschine , die wie folgt funktioniert: Bei Eingaben der Länge simuliert sie auf für Schritte. Wenn akzeptiert, schleife für Schritte und halte an; Ansonsten Schleife für Schritte und Stopp.M ' n M x n M n 2 n 3(M,x)MnMxnMn2n3

Wenn auf stoppt tut sie dies in Schritte, um die Laufzeit von wäre . Wenn niemals anhält beträgt die Laufzeit von mindestens .x t = O ( 1 ) M ' O ( n 2 ) M M ' n 3Mxt=O(1)MO(n2)MMn3

Daher kann man entscheiden , ob akzeptiert von der Entscheidung , ob die Laufzeit von ist oder .x M ' O ( n 2 ) O ( n 3 )MxMO(n2)O(n3)

Manu
quelle
4
Warum muss M in O (1) Schritten an x ​​anhalten (falls ja)?
Suresh Venkat
10
und x sind unabhängig von n fest . Mxn
Manu
2
Sehr kluger Beweis, ist es eine Variation eines bekannten Ergebnisses oder haben Sie es einfach ausgedacht?
Antonio E. Porreca
3
@Raphael: Das ist ein heikler Bereich, den wir meines Erachtens nicht gelöst haben. Einige Stack-Exchange-Sites unterstützen die Bearbeitung der Antworten anderer. Wir haben keine Politik dagegen, aber praktisch gesehen habe ich es fast nie getan. Ein technischer Punkt: Wenn eine Antwort zu stark bearbeitet wird, wird sie zum Community-Wiki, und @Emanuele würde keine weiteren Wiederholungspunkte erhalten, wenn seine Antwort danach hochgestuft würde. Ich denke, eine zusätzliche Erklärung würde helfen zu klären: @ John Sidles dachte anfangs, dass das Versprechen nicht verwendet wurde, aber der Beweis verwendet ein stärkeres Versprechen: läuft in n 2 oder n 3 , nicht nur in P.Mn2n3
Aaron Sterling
2
@ John: Solange keine veröffentlichte Referenz angegeben ist, sollten Sie diese Richtlinie berücksichtigen .
Raphael
29

Dies ist eine Umformulierung der Antwort von Emanuele Viola mit dem Ziel, verständlicher zu werden.

Wir zeigen, dass das gegebene Problem unentscheidbar ist, indem wir das allgemeine Halteproblem H darauf reduzieren .PH

Sei eine beliebige Instanz des Halteproblems, dh wir müssen entscheiden, ob M ( x ) ( M bleibt auf x ). Konstruieren Sie eine Turingmaschine M * , die wie folgt funktioniert:(M,x)M(x)MxM

M*(y) = {
  n := |y|
  Simulate M(x) for n steps
  if ( M(x) has halted )
    Execute n*n arbitrary steps
  else
    Execute n*n*n arbitrary steps
}

Jetzt beobachten wir die folgenden Implikationen:

M(x)n0N:M halts on x after at most n0 stepsy:nn0M(y) executes n2 arbitrary stepsTM(n)O(n2)

und

M(x)nN:M does not halt on x in less than n stepsy:M(y) executes n3 arbitrary stepsTM(n)Ω(n3)

H(M,x)P(M,2)PH

Raphael
quelle
12

nCn+DC,DN

Cn+D

Andrej Bauer
quelle
1
Kein Mangel an ungewöhnlichem Verhalten bei kleinen Ein-Band-TMs. :)
Kaveh
4

Das Problem wurde auch in meinem Artikel " Der intensive Inhalt von Rices Theorem " POPL'2008 gelöst, in dem ich beweise, dass keine "Komplexitäts-Clique" entscheidbar ist. Eine Komplexitätsclique ist eine Klasse von Programmen, die für Programme mit ähnlichem Verhalten und ähnlicher Komplexität geschlossen sind. Ich biete auch die notwendigen Bedingungen für teilentscheidbare Eigenschaften.

Programme, die in O (n ^ k) laufen, sind eine Komplexitätsklasse im obigen Sinne, daher ist die Menge nicht entscheidbar.

Das Ergebnis wurde kürzlich auch auf subrekursive Einstellungen (wie P) von Mathieu Hoyrup erweitert: Die entscheidbaren Eigenschaften von subrekursiven Funktionen (ICALP 2016).

Andrea Asperti
quelle
2

Σ20

Um die Vollständigkeit zu klären, während die P-Zeit Versprechen Bedingung ist auch -komplette, gibt es eine Reihe von Codes entscheidbar , so dass alle Maschinen in sind Polynomzeit und das Frage ist Ergänzen auf . SSO( n 2 )0 2 SΣ20SSO(n2)Σ20S

Um dies zu beweisen, wählen Sie ein vollständiges , mit berechenbarer Polynomzeit (für Binärzahlen). & phiv; & phiv; (x) k mΣ20φψφ(x)kmψ(x,k,m)ψ

Dann gilt wenn die folgende MaschineO ( n 2 )φ(x)O(n2)n

kn
m<nψ(x,k,m)

n2

cn2+cΠ10Σ20

Dmytro Taranovsky
quelle
-1

Hier sind neue systematischere Analysen / Winkel / Ergebnisse zu dieser Frage und verwandte, die das Konzept der "algorithmischen Verifizierbarkeit" und ein Reis-ähnliches Analogon für die Komplexitätstheorie einführen. Es folgt ein relevanter Abschnitt aus der Zusammenfassung, und es gibt viele andere verwandte Theoreme, die sich auf die Beweisbarkeit von P gegen NP usw. beziehen

  • Warum das Konzept der rechnergestützten Komplexität für die nachprüfbare Mathematik schwierig ist / Hromkovic

    Zunächst beweisen wir Rices Theorem für die Unbeweisbarkeit und behaupten, dass nicht jedes nichttriviale semantische Problem über Programme in der algorithmisch nachprüfbaren "AV" -Mathematik fast überall lösbar ist. Damit zeigen wir, dass es unendlich viele Algorithmen gibt (Programme, die nachweislich Algorithmen sind), für die es keine Beweise dafür gibt, dass sie in Polynomzeit arbeiten oder dass sie nicht in Polynomzeit arbeiten. ...

    Es ist zu beachten, dass, wenn P! = NP in der AV-Mathematik nachweisbar ist, für jeden Algorithmus A nachweisbar ist, dass "A die ZUFRIEDENHEIT nicht löst oder A in der Polynomzeit nicht funktioniert". Interessanterweise zeigen wir schließlich, dass es Algorithmen gibt, für die weder bewiesen werden kann, dass sie nicht in polynomialer Zeit funktionieren, noch dass sie die ZUFRIEDENHEIT nicht lösen. Darüber hinaus gibt es einen Algorithmus zur Lösung von SATISFIABILITY, für den man in der AV-Mathematik nicht nachweisen kann, dass er in polynomialer Zeit nicht funktioniert.

    Weiterhin zeigen wir, dass P = NP die Existenz von Algorithmen X impliziert, für die die Behauptung "X löst ZUFRIEDENHEIT in der Polynomzeit" in der AV-Mathematik nicht nachweisbar ist.

vzn
quelle
-3

Die Lösung von Viola kann auf jede Laufzeit (über poly hinaus) verallgemeinert werden: Sie können das Problem des Anhaltens wie folgt darauf reduzieren. Konstruieren Sie für eine Instanz (M, x) des Halteproblems eine neue Maschine M ', die wie folgt funktioniert: Bei Eingaben der Länge n simuliert sie M auf x für f (n) Schritte oder bis M anhält, wobei f (n) ) ist eine beliebige ansteigende Funktion (größer als die Konstante) von n. (Obs .: M 'liest allmählich die Eingabe, um zu vermeiden, dass lineare Zeit [O (n)] verschwendet wird, nur um unnötig die gesamte Eingabe zu lesen, wenn sie groß genug ist und M anhält.)

Wenn M an x ​​anhält, geschieht dies in Schritten von T = O (1), so dass die Laufzeit von M 'O (1) wäre. Wenn M niemals anhält, ist die Laufzeit von M 'O (n ^ 2 · f (n)).

Sie können also entscheiden, ob M x akzeptiert, indem Sie entscheiden, ob die Laufzeit von M 'O (1) oder O (n ^ 2 * f (n)) ist.

Dann kann der Hilfscode von Raphael wie folgt verallgemeinert werden:

Sei (M, x) eine beliebige Instanz des Halteproblems, das heißt, wir müssen entscheiden, ob M an x ​​anhält. Konstruieren Sie eine deterministische Turing-Maschine (DTM) M *, die wie folgt funktioniert:

  1. M * (Eingabe) = {
  2. n: = 0
  3. Lesen Sie das erste Symbol von der Eingabe
  4. Schleife:
  5. n: = n + 1
  6. Simulieren Sie M (x) für f (n) Schritte oder bis M (x) anhält
  7. Lesen Sie das nächste Symbol von der Eingabe
  8. Schleife, bis end_of_input oder bis M (x) angehalten hat
  9. }

Jetzt beobachten wir die folgenden Implikationen:

M hält an x ​​nach höchstens k (konstanten) Schritten an => T (M *) = O (1) und

M hält nie an x ​​=> T (M *) = O (n ^ 2 * f (n))

Selbst zu entscheiden, ob die Laufzeit eines beliebigen DTM einfach größer als die Konstante ist, ist daher genauso schwierig wie das Problem des Anhaltens. □

André Luiz Barbosa
quelle
2
MO(n)M
Wenn M (x) für n, das groß genug ist, anhält, wird auch seine Simulation angehalten und kehrt innerhalb von n0 (konstanten) Schritten zu M * zurück.
André Luiz Barbosa