Enthält P unverständliche Sprachen? (TCS Community Wiki)

Antwort: nicht bekannt

Vielen Dank an alle, die dazu beigetragen haben, diese Frage und die damit verbundenen Definitionen zu verfeinern.

Die Definitionen dieses Wikis bildeten den Ausgangspunkt für das neuere TCS-Wiki " Enthält P Sprachen, deren Existenz unabhängig von PA oder ZFC ist? (TCS-Community-Wiki) ".

Das neuere Wiki wird bevorzugt, da seine Definitionen und Nomenklaturen wesentlich komplexer sind als die dieses älteren Wikis.

Insbesondere diese Nomenklatur ältere Wiki unverständlich verständliche Sprachen und TMs wird in der neueren Wiki von verdrängtem kryptischen gnostischen . Abgesehen von Definitionsdetails - die jedoch wichtig sind - sprechen die beiden Wikis eine ähnliche Klasse von Fragen an. $\Leftrightarrow$ $\Leftrightarrow$

Weitere Antworten sind willkommen

Weitere Antworten sind willkommen (natürlich), und es ist wahrscheinlich, dass eine weitere definitive Abstimmung angemessen ist. Eine wichtige Lehre war, dass diese Klasse von Fragen schwierig zu formulieren und noch schwieriger zu beantworten ist.

Als Hintergrund wurde die Antwort von Sasho Nikolov mit "akzeptiert" bewertet, da sie eine Formulierung lieferte, die die Absicht der Frage festhielt: Die Antwort auf die Frage ist (anscheinend) nicht bekannt.

Die wertvolle Antwort von Philip White motivierte die abgestufte Definition von TMs, die unverständlich oder stark unverständlich oder kanonisch unverständlich sind (gemäß der Liste "abgestufte Definitionen von Unverständlichkeit" unten).

Die folgende Erklärung der Frage enthält vorläufig wertvolle Erkenntnisse und Vorschläge von Tsuyoshi Ito, Marzio De Biasi, Huck Bennett, Ricky Demer und Peter Shor sowie einen wertvollen Weblog-Beitrag von Luca Trevisan .

Formale Definition

Unverständliche Turingmaschinen werden (innerhalb von ZFC) wie folgt definiert:

D1 Bei einer Turing-Maschine M, die nachweislich für alle Eingabezeichenfolgen anhält, wird M als unverständlich bezeichnet, wenn die folgende Aussage für mindestens eine positive semidefinite reelle Zahl weder beweisbar noch widerlegbar ist : $r$

Anweisung: Ms Laufzeit ist in Bezug auf die Eingabelänge ${O}(n^r)$ $n$

Umgekehrt heißt M verständlich, wenn es nicht unverständlich ist.

Disambiguating entscheidbar

Der Wikipedia-Eintrag " Unentscheidbares Problem: Beispiele für unentscheidbare Aussagen " gibt einen kurzen Überblick über die unterschiedlichen Sinne des Begriffs "unentscheidbar", die in der Literatur zu Beweistheoretik und Berechenbarkeitstheorie üblich sind. Um Mehrdeutigkeiten zu vermeiden, verwenden die gestellten Definitionen und Fragen ausschließlich die Terminologie "weder nachweisbar noch widerlegbar".

Weitere Referenzen in dieser Hinsicht sind Jeremy Avigads Kursnotizen " Unvollständigkeit über das Halteproblem ", Scott Aaronsons Weblog-Aufsatz " Rossers Theorem über Turing-Maschinen " und Luca Trevisans Weblog-Beitrag Zwei interessante Fragen .

Über die Existenz unverständlicher Turingmaschinen

Dass es unverständliche Turing-Maschinen gibt, ergibt sich konkret aus einer Konstruktion von Emmanuele Viola und weitgehend aus dem komplexitätstheoretischen Rahmen von Juris Hartmanis. Insbesondere liefert Violas Konstruktion über die Methoden der Kursnotizen von Jeremy Avigad (so wie ich sie verstehe) das folgende Lemma:

$\to$

Respektierung der Natürlichkeit bei der Definition von Unverständlichkeit

Es ist natürlich zu fragen, ob die umgekehrte Implikation zu Violas Implikation wahr ist.

Überlegungen zur Natürlichkeit erfordern, dass die umgekehrte Implikation sorgfältig gestellt wird, indem der Kommentar von Philip White unten zeigt, wie unverständliche TMs über Polylimiter , die Rechenmodule sind, die ( tatsächlich ) die Laufzeit einer unverständlichen Maschine so " auffüllen" , trivial auf verständliche TMs reduziert werden können um es auf eine verständliche Maschine zu reduzieren.

Insbesondere ist es selbstverständlich zu verlangen, dass wir „ alte Elemente der Unverständlichkeit nicht unästhetisch maskieren, indem wir neue Elemente der Unverständlichkeit einführen “. Die zentrale Herausforderung im Zusammenhang mit der gestellten Frage lautet: "Gibt es eine natürliche Definition von Unverständlichkeit?" … Was wir (angesichts der Diskussion hier über TCS) vielleicht als eine nicht triviale Meta-Frage betrachten sollten, die mehr als eine natürliche Antwort haben kann.

Im Hinblick auf dieses Leitprinzip der Natürlichkeit werden abgestufte Definitionen von Unverständlichkeit wie folgt spezifiziert.

Benotete Definitionen von Unverständlichkeit

$r$ $r$

D3 Wir sagen, dass eine Sprache L unverständlich ist, wenn sie von (a) mindestens einer Turingmaschine M akzeptiert wird, die sowohl effizient als auch unverständlich ist, und außerdem (b) es kein effizientes und verständliches TM gibt, das nachweislich (in ZFC) akzeptiert L. L.

D4 Wir sagen, dass ein unverständliches TM stark unverständlich ist, wenn die Sprache, die es akzeptiert, unverständlich ist.

D5 Wir sagen, dass ein stark unverständliches TM kanonisch unverständlich ist, wenn es effizient ist.

Diese Definitionen stellen sicher, dass jede unverständliche Sprache von mindestens einem TM akzeptiert wird, das kanonisch unverständlich ist, und dass es im Hinblick auf D3 (a) und D3 (b) keine triviale Polylimiter-Reduktion eines kanonisch unverständlichen TM zu einem verständlichen TM gibt das erkennt nachweislich die gleiche Sprache.

Die drei Fragen gestellt

Q1 Enthält die Komplexitätsklasse P unverständliche Sprachen?

F2 Kann mindestens eine unverständliche Sprache konkret dargestellt werden? (Wenn ja, geben Sie ein konstruktives Beispiel an).

F3 Kann mindestens ein kanonisch unverständliches TM konkret dargestellt werden? (Wenn ja, geben Sie ein konstruktives Beispiel an).

Motivation

Die unverständlichen Eigenschaften der Komplexitätsklasse P behindern das Verständnis einer breiten Klasse von Problemen, zu denen (für den ursprünglichen Antragsteller dieser Frage ) Terry Taos Blue-Eyed Islanders Puzzle , Dick Lipton und Ken Regans Urn-Choice-Spiel sowie deren Hybridisierung gehören der Kontext von Newcombs Paradoxon über das Balanced Advantage Newcomb Game .

Wie Juris Hartmanis 'Monographie Machbare Berechnungen und nachweisbare Komplexitätseigenschaften (1978) es ausdrückt:

Die Ergebnisse über die Komplexität von Algorithmen ändern sich radikal, wenn wir nur Eigenschaften von Berechnungen berücksichtigen, die formal bewiesen werden können.

Der Kampf um die Erstellung gut gestellter Definitionen und Postulate, die Hartmanis 'Einsichten erfassen, hilft uns, besser zu verstehen, dass die Komplexitätsklasse P einige äußerst eigenartige Sprachen enthält, die von äußerst eigenartigen Turing-Maschinen erkannt werden, deren Eigenschaften wir (derzeit) sind ) sehr weit vom Greifen entfernt. Es fällt auf, dass derzeit im strengsten Sinne nicht bekannt ist, ob die Komplexitätsklasse P nachvollziehbar ist.

Vielen Dank an alle, die Kommentare und Antworten beigesteuert haben.

cc.complexity-theory complexity-classes turing-machines decidability John Sidles
quelle

Bitte definieren Sie den Begriff "(eine Turingmaschine) ist in P. entscheidend."

Tsuyoshi Ito

Was genau ist bei dem in der Definition von „unverständlich in P“ angegebenen Problem die Eingabe? Ist die Turingmaschine Teil des Eingangs oder fest? Wie wird außerdem eine reelle Zahl als Zeichenfolge angegeben?

Tsuyoshi Ito

r

$r$

M

$M$

Wie Sasho präventiv erklärte, ist das in der Definition von „unverständlich“ in Revision 4 angegebene Problem für jeden M entscheidbar. Ich befürchte, dass Sie hier einen elementaren Fehler machen. Wenn Sie immer noch Probleme haben, es zu verstehen, kann dieser Beitrag von Raphael und der Link darin hilfreich sein. Ich habe dafür gestimmt, dies als keine wirkliche Frage zu schließen.

Tsuyoshi Ito

C n^{k}

$Cn^k$

C

$C$

k

$k$

Antworten:

(Ich ziehe den Teil der Antwort, der gerade erklärt hat, warum es keine unentscheidbaren Instanzen eines Problems / keine Polytime-Algorithmen mit nicht berechenbarer Zeitbindung gibt, als nicht mehr relevant zurück. )

$T$ $M$ $M$ $T$

$M$ $M$
$M$ $M'$

Die Antwort auf Ihre Frage scheint also "Nein" zu sein: Jede Sprache, die in Polytime von einer Maschine bestimmt werden kann, wird von einer nachweislich Polytime-Maschine entschieden. Aber vielleicht sollte Ihre Frage sein:

$M$ $M'$ $M$

Ich vermute, dass die Antwort ja ist, aber im Moment habe ich keine Zeit mehr, mich dem zu widmen.

Sasho Nikolov
quelle

------ Es gibt zwei verschiedene Sinne des Wortes, die in Mathematik und Informatik unentscheidbar sind . Der erste davon ist der beweistheoretische Sinn, der in Bezug auf Gödels Theoreme verwendet wird, nämlich der einer Aussage, die in einem bestimmten deduktiven System weder beweisbar noch widerlegbar ist. ... Aufgrund der beiden Bedeutungen des Wortes unentscheidbar wird der Begriff unabhängig manchmal für den Sinn "weder beweisbar noch widerlegbar" anstelle von unentscheidbar verwendet.

John Sidles

Danke, Sasho! Ich bin auch zu dieser Erkenntnis gekommen, aber das Postulat kann durch die Unterscheidung von Wikipedia geändert werden: "Es gibt zwei verschiedene Sinne des Wortes, die in Mathematik und Informatik unentscheidbar sind . Der erste davon ist der beweistheoretische Sinn, der in Bezug auf Gödels Theoreme verwendet wird. die einer Aussage, die in einem bestimmten deduktiven System weder beweisbar noch widerlegbar ist ... Aufgrund der beiden Bedeutungen des Wortes unentscheidbar wird der Begriff unabhängig manchmal verwendet, anstatt unentscheidbar für den Sinn 'weder beweisbar noch widerlegbar'. " Daher hoffe ich, die Frage später heute zu klären.

John Sidles

Aufgrund Ihrer nachdenklichen Kommentare wurde das mehrdeutige Attribut "entscheidbar" jetzt durch das (hoffentlich eindeutige) Attribut "weder nachweisbar noch widerlegbar" ersetzt. Dafür wird Ihre Hilfe geschätzt und gedankt.

John Sidles

Bitte überprüfen Sie meine aktualisierte Antwort

Sasho Nikolov

Danke, Sasho. Auch ich muss bis morgen eine Pause machen, aber bei der ersten Lesung scheint Ihr letzter Vorschlag sehr fruchtbar zu sein, und ich hoffe, bald darauf antworten zu können. Danke noch einmal.

John Sidles

Nur ein ausführlicher Kommentar, der versucht, die Frage zu interpretieren.

$M$ ~~wird versprochen anzuhalten~~ $M$ ~~positive semidefinite reelle Zahl~~ $r$ ~~Frage~~ $Q_{M,r}$

OPTION 1

$Q_{M,r}(n)$ $M$ $n^r$ $n$

$2^n$ $M$ $\Rightarrow$

OPTION 2

$Q_{M,r}$ $M$ $O(n^r)$

$\Rightarrow$

Und wenn Sie fragen: "Ok, aber können wir den Wert 1 oder 0 berechnen, um den Algorithmus zu erstellen, der die Frage nach Option 2 beantwortet?", Dann greifen wir auf Folgendes zurück:

$Q_{r}(M)$ $M$ $O(n^r)$ $M$

Marzio De Biasi
quelle

Marzo, danke für diese Antwort und für deinen Kommentar oben. Der mehrdeutige Begriff "entscheidbar" wurde bereits gestrichen - er bedeutete für verschiedene Gemeinschaften verschiedene Dinge - zugunsten der beweistheoretischen Redewendung "weder beweisbar noch widerlegbar". Der Warteschlange zur Klärung von Änderungsanträgen für die bearbeitete Version der Frage von morgen (die hoffentlich die endgültige strenge Aufstellung der Frage sein wird) wird gemäß Ihrer Option 1 der Satz "Für alle n " vorangestellt. Und schließlich werden Anerkennung und Dankbarkeit erweitert Ihnen und allen um Hilfe bei der rigorosen und klaren Beantwortung der Frage.

John Sidles

M

$M$

M

$M$

O (n^{r})

$O(n^r)$

M

$M$

O (n^{r})

$O(n^r)$

Marzo, OK und danke. Um "Violas Implikation" festzustellen, müssen wir das Argument aus Abschnitt 3 der Kursnotizen von Jeremy Avigad (wie in der Frage verlinkt) an Violas Konstruktion anhängen ... die geänderte Frage wird diesen Punkt klarstellen. Unnötig zu erwähnen, dass der Prozess der Klärung von Definitionen 10X ++ schwieriger war als ursprünglich angenommen ... was vielleicht ein Hauptpunkt der Frage ist. Danke noch einmal.

John Sidles

Die Antwort auf Ihre Frage Nr. 1 lautet definitiv "Nein". Wie ich glaube, hat jemand im (sehr langen) Kommentarbereich darauf hingewiesen, dass Sie einer Maschine leicht ein "Polylimiting" hinzufügen können. Das heißt, selbst wenn Sie nicht wissen, was r ist, wenn Sie eine ganze Zahl größer als r erraten (dies ist natürlich offensichtlich möglich), können Sie eine Overhead-Maschine einrichten, die Ihre "unverständliche" Turing-Maschine simuliert, und sie erzwingen in Polynomzeit aufhören zu laufen ... ohne die Sprache zu ändern, die die Turing-Maschine überhaupt akzeptiert. Auf diese Weise können Sie jede "unverständliche" Polynomzeit-Turingmaschine in eine "verständliche" Polynomzeit-Turingmaschine umwandeln, was bedeutet, dass es in P keine Sprache gibt, die ausschließlich von "unverständlichen" Turingmaschinen entschieden werden kann.

Ich hoffe das hilft. Wenn ich Ihre Frage und Ihre Absicht nicht völlig falsch interpretiert habe, ist meine Antwort mit Sicherheit richtig. Es ist überhaupt keine offene Frage.

Philip White
quelle

Übrigens, wenn Sie ein gutes Beispiel für einen Kandidaten für einen von Ihnen als "unverständlich" bezeichneten Algorithmus suchen , lesen Sie " Scholarpedia.org/article/Universal_search" . Der universelle Suchalgorithmus zur Lösung von SAT entspricht Ihrer Definition von unverständlich, wenn P = NP formal unabhängig ist.

Philip White

Wissen Sie etwas über die letzte Frage aus meiner Antwort? Ich glaube, das ist die einzige Frage, die immer noch nicht offensichtlich trivial ist. Für mich ist das

Sasho Nikolov

@Philip White, die Definition wurde sorgfältig erstellt, um der von Ihnen bereitgestellten Konstruktion zu entgehen. Angenommen, die Laufzeit von M ist für einen Exponenten r unentscheidbar , und wir schätzen einen Wert r ' > r , und wir installieren einen r' - Polylimiter in einer modifizierten Maschine M', die dieselbe Sprache wie M erkennt, dann für M 'die Anweisung "Die Laufzeit von M 'ist O (n ^ r) in Bezug auf die Eingangslänge n" ist immer noch unentscheidbar. Ich stimme jedoch zu, dass wir sorgfältig darüber nachdenken müssen, ob ALLE Katz-und-Maus-Spiele mit Orakel-spezifischen Polylimitern ausgeschlossen sind (wie beabsichtigt) - und deshalb habe ich Ihre Antwort positiv bewertet!

John Sidles

Oh, und da sich Sashos Kommentar mit meinem überschneidet, möchte ich meine Wertschätzung für die letzte Frage in Sashos Antwort zum Ausdruck bringen , die (nach meinem derzeitigen Verständnis) die Einführung von aus Orakeln stammenden Polylimitern kunstvoll behindert. Nach wie vor muss ich ein oder zwei Tage darüber nachdenken. Nochmals vielen Dank, Philip.

John Sidles

Entschuldigung, ich hätte die Antwort von Sasho Nikolov genauer lesen sollen. Ich habe gerade das Wort "Ja" gesehen. Ich werde gleich auf die letzte Frage schauen und sehen, ob ich etwas Nützliches zu sagen habe.

Philip White