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 ) 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.
quelle
Antworten:
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) M′ n M x n M n2 n3
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 3M x t=O(1) M′ O(n2) M M′ n3
Daher kann man entscheiden , ob akzeptiert von der Entscheidung , ob die Laufzeit von ist oder .x M ' O ( n 2 ) O ( n 3 )M x M′ O(n2) O(n3)
quelle
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 .P H
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)↓ M x M∗
Jetzt beobachten wir die folgenden Implikationen:
und
quelle
quelle
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).
quelle
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Σ02 S S O(n2) Σ02 S
Um dies zu beweisen, wählen Sie ein vollständiges , mit berechenbarer Polynomzeit (für Binärzahlen). & phiv; & phiv; (x)⇔ ∃ k ∀ mΣ02 φ ψφ(x)⇔∃k∀mψ(x,k,m) ψ
Dann gilt wenn die folgende MaschineO ( n 2 )φ(x) O(n2) n
quelle
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
quelle
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:
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. □
quelle