Stellen die unentscheidbaren Eigenschaften von P ein Hindernis für die Entscheidung zwischen P und NP dar? (Antwort: vielleicht)

Es werden fünf verknüpfte Fragen gestellt und eine einzige integrierte Antwort erhofft:

• Frage 1 : Gibt es Sprachen , die nur von den Turing-Maschinen in  erkannt werden, deren Laufzeitexponenten unentscheidbar sind ?$L$$P$
• F2: Können Beispiele dieser Turingmaschinen endlich gebaut werden?
• F3: Können diese Turing-Maschinen konkret instanziiert werden? ( zB durch Orakel, die sie "erraten", anstatt sie endlich zu konstruieren).
• Frage 4: Welche anderen Attribute von P (außer Laufzeitexponenten) sind derzeit als unentscheidbar bekannt? Für welche Attribute von ist diese Frage offen?$P$
• Frage 5: Stellen die unentscheidbaren Eigenschaften von ein Hindernis für die Entscheidbarkeit von ?P ≠ N P$P$$P \ne NP$

Notieren Sie sorgfältig das Wort "nur" in Q1 (das die von Lance Fortnow vorgeschlagene Antwort ausschließt).

Schlussfolgerungen und Umstellung auf Community Wiki

• Die Frage "Stellen die unentscheidbaren Eigenschaften von P ein Hindernis für die Entscheidung zwischen P und NP dar?" Ist offen und wird als schwierig angesehen, ebenso wie zahlreiche spezifische Fragen (wie Q1–4 oben), die natürlich damit verbunden sind.

• Juris Hartmanis '1978 erschienene Monographie Machbare Berechnungen und nachweisbare Komplexitätseigenschaften bieten einen guten Einstieg in die Literatur, und (anscheinend) wurde seit Hartmanis' keine Rezension veröffentlicht.

• Diese Klasse von Fragen ist so wenig erforscht, dass die Herausforderung, strenge Beweise zu finden, eng mit der Herausforderung verbunden ist, gute Ausgangsdefinitionen zu wählen.

• Die nachdenklichen Bemerkungen und aufschlussreichen Beweisskizzen von Travis Service und Alex ten Brink werden anerkannt und geschätzt.

Da die Frage offen ist und in mehreren mathematischen Weblog-Threads ( 1 , 2 , 3 , 4 , 5 , 6 ) diskutiert wird , wurde diese Frage für die Konvertierung in das Community-Wiki markiert.

Update II und Zusammenfassung

Mir ist bewusst geworden, dass Juris Harmanis '1978 erschienene Monografie Machbare Berechnungen und nachweisbare Komplexitätseigenschaften als eine eingehende Antwort auf Q1–5 gelesen werden kann . Darüber hinaus bieten die (ausgezeichneten) Q1- und Q4- Proof-Skizzen von Travis Service und Alex ten Brink eine moderne Bestätigung und Erweiterung der allgemeinen Schlussfolgerungen von Hartmanis:

Ergebnisse über die Komplexität von Berechnungen ändern sich radikal, wenn wir nur Eigenschaften von Berechnungen betrachten, die formal bewiesen werden können (Hervorhebung durch Hartmanis) ...

Daher ist zu erwarten, dass die Ergebnisse über die Optimalität aller Programme, die dieselbe Funktion wie ein gegebenes Programm berechnen, von den Optimalitätsergebnissen über alle Programme abweichen, von denen formal nachgewiesen werden kann, dass sie dem gegebenen Programm äquivalent sind. ...

Wir sollten die Möglichkeit in Betracht ziehen, dass dieses berühmte Problem [ ] in einer formalisierten mathematischen Theorie wie der Mengenlehre möglicherweise nicht lösbar ist.$P\overset{?}{=}NP$

Sowohl aus der Monographie von Hartmanis als auch aus den Antworten von Travis und Alex geht hervor, dass Q1–5 den gegenwärtigen Stand der Komplexitätstheorie deutlich übersteigt . Darüber hinaus sind diese Fragen / Antworten offensichtlich so subtil, dass sie sorgfältige definitorische Anpassungen erfordern und Darstellungen in Monografielänge rechtfertigen. Ich hoffe, dass sie die Menschen nicht davon abhalten, weitere Antworten zu veröffentlichen. :)

Weitere technische Informationen finden Sie in der Antwort von Joel David Hamkins auf die Frage MathOverflow. Kann ein Problem gleichzeitig polynomiell und unentscheidbar sein? (Empfohlen von Alex ten Brink).

Ersetzt man in Hartmanis 'Monographie den Ausdruck "Simulation der Dynamik" durch "Berechnung der Funktionen", so kann das Ergebnis als Abhandlung über die komplexitätstheoretischen Grenzen der Systemtechnik gelesen werden Probleme.

Eine gegenläufige Meinung zu Hartmanis 'hat Oded Goldreich kürzlich in einem Brief an den CACM-Herausgeber mit dem Titel "On Computational Complexity" geäußert :

Leider fehlen uns derzeit gute theoretische Antworten auf die meisten natürlichen Fragen zur effizienten Berechnung. Dies ist nicht der Fall, weil wir die falschen Fragen stellen, sondern weil diese Fragen sehr schwierig sind.

Es ist (natürlich) durchaus vorstellbar, dass sich sowohl Hartmanis 'als auch Goldreichs Ansichten als richtig erweisen, zum Beispiel könnte ein formaler Beweis für die Unentscheidbarkeit der Trennbarkeit von PvsNP vernünftigerweise als Bestätigung beider Standpunkte angesehen werden.

Aktualisiere ich

Nachdenkliche Kommentare (unten) von Travis Service und Alex ten Brink legen nahe, dass der Ausdruck "unentscheidbar" im ersten Quartal nicht gleichbedeutend mit "nicht nachweisbar entscheidbar" ist und dass die Antworten auf Q2–5 möglicherweise von dieser Unterscheidung abhängen. Es ist (für mich) überhaupt nicht klar, welche definitorische Wahl zu den stärksten Theoremen führen würde, und es ist auch am besten, unsere Intuition der Klasse P zu erfassen. Antworten und Kommentare, die sich mit dieser Frage befassen, sind willkommen.

Eine Bemerkung von Felix Klein in seiner Elementarmathematik aus fortgeschrittener Sicht: Geometrie (1939) fällt ein:

Ein weiteres Beispiel für ein Konzept, das in der naiven Raumwahrnehmung mehr oder weniger präzise auftritt und das wir als Ergänzung zu unserem Geometriesystem hinzufügen müssen, ist der Begriff einer (willkürlichen) Kurve . Jeder Mensch glaubt zu wissen, was eine Kurve ist, bis er so viel Mathematik gelernt hat, dass die unzähligen möglichen Abnormalitäten ihn verwirren.

Wie bei Kurven auch bei den Sprachen, die von Turing-Maschinen in  … akzeptiert wurden. Was mir früher als die einfachste und natürlichste aller Komplexitätsklassen erschien, verwirrt mich jetzt durch die (unzähligen?) Nicht überprüfbaren und / oder unentscheidbaren Eigenschaften seiner Mitglieder . Die allgemeine Motivation, Q1–5 zu fragen, bestand darin, einen Weg durch dieses verwirrende Dickicht zu finden, aber die bisherigen Antworten (von Travis Service und Alex ten Brink) haben weitere Verwirrung gestiftet!$P$

Kleins Generation von Mathematikern bemühte sich sehr, gute Definitionen für Kurven und andere grundlegende Elemente der Mengenlehre, -geometrie und -analyse zu finden. Eine Übersicht auf Elementarebene finden Sie in der Wikipedia-Diskussion zur Alexander Horned Sphere

      
      Einbetten einer Kugel in R3

Während des 20. Jahrhunderts half die Analyse von "wilden Mannigfaltigkeiten" wie der Alexander-Kugel, die Unterscheidung zwischen topologischen Mannigfaltigkeiten, stückweise kontinuierlichen Mannigfaltigkeiten und Differential-Mannigfaltigkeiten zu klären. Ebenso im 21. Jahrhundert, vielleicht Verfeinerungen der zu zugehörigen Definitionen werden zahm helfen ‚s wilde Sprachen und wilde Turingmaschinen ... obwohl geeignete Verfeinerungen Angabe wird keine leichte Aufgabe sein.$P$$P$

Hintergrund

Diese verknüpften Fragen ergeben sich aus den MathOverflow Community Wiki Fragen „ Was sind die attraktivsten Turing unentscheidbar Probleme in der Mathematik sind? “ Und „ Was Begriffe verwendet werden , aber nicht eindeutig in der modernen Mathematik definiert? “ Insbesondere Colin Tan beantragt , dass die Frage oben gefragt sein als separate Frage gestellt.

Zum technischen Hintergrund siehe die TCS StackExchange- Frage " Sind Laufzeitgrenzen in P bestimmbar? ", Insbesondere Emanuele Violas prägnanter Beweis, dass die Antwort "Nein" ist. Beachten Sie auch, dass ähnliche Ergebnisse von Juris Hartmanis in seiner Monografie Machbare Berechnungen und nachweisbare Komplexitätseigenschaften (1978) belegt werden.

Das Weblog von Lance Fortnow / Bill GASARCH, Computational Complexity, veranstaltet diese Woche seine dekadische Umfrage " Does or Not?$P=NP$ " - die fünfte und letzte gestellte Frage lädt zum Kommentieren der Fortnow / GASARCH-Frage ein.

Für Frage 1 lautet die Antwort nein. Lassen eine Sprache in und lassen Turing - Maschine zu erkennen jede Polynom Zeit (deren Laufzeit wird davon ausgegangen sein unentscheidbar). Für jedes sei die Turingmaschine, die bei Eingabe von der Länge zuerst für Schritte eine Schleife , dann für Schritte auf und akzeptiert, wenn akzeptiert (innerhalb von diese Schritte) und lehnt ansonsten ab. Die Laufzeit von istP M L k ∈ N M K x n n k M x n k + k M x n k + k M k Θ ( n k ) für jedes k .$L$$P$$M$$L$$k \in \mathbb{N}$$M_k$$x$$n$$n^k$$M$$x$$n^k + k$$M$$x$$n^k + k$$M_k$$\Theta(n^k)$$k$

Da in der Polynomzeit läuft, gibt es einige k ' ∈ N, so dass M in O ( n k ' ) läuft (auch wenn wir nicht wissen, was k ' ist) und daher für alle k groß genug ist, erkennt M k L und hat eine entscheidbare Laufzeit.$M$$k' \in \mathbb{N}$$M$$O(n^{k'})$$k'$$k$$M_k$$L$

BEARBEITEN

Ich denke, die folgende Antwort entspricht eher dem, was das Originalplakat mit Frage 1 beabsichtigt hatte.

Satz: Es gibt eine Sprache so dass, wenn N eine Turing-Maschine ist, die L entscheidet, mindestens eine der folgenden Aussagen zutrifft:$L \in P$$N$$L$

1) Es gibt keinen Beweis, dass L akzeptiert , oder$N$$L$

2) Es gibt keinen Beweis dafür, dass in f ( n ) Schritten anhält (für jede Funktion f ( n ) ).$N$$f(n)$$f(n)$

Beweisskizze: Sei eine Turing-Maschine, die nicht auf dem leeren Band anhält und für die es keinen Beweis gibt, dass M nicht auf dem leeren Band anhält (Independence ergibt in Computer Science von Hartmanis und Hopcroft eine solche M- Dose) effektiv gefunden werden).$M$$M$$M$

Es sei .$L = \{ n : \exists n' \geq n \mbox{ s.t. } M \mbox{ halts in } n' \mbox{ steps when run blank tape}\}$

Da nicht anhält, ist L tatsächlich die leere Sprache, aber es gibt keinen Beweis dafür (da dies beweisen würde, dass M nicht anhält).$M$$L$$M$

Sei irgendeine Turingmaschine. Wenn es sowohl einen Beweis gibt, dass N L entscheidet, als auch einen Beweis, dass N in f ( n ) Schritten abläuft, dann liefert die Ausführung von N bei Ausführung an Eingang 1 entweder einen Beweis, dass M anhält (dh, wenn N akzeptiert), oder dass M dies tut nicht anhalten (dh, wenn N ablehnt). Wenn also N beweisbar entscheidet L dann N ‚s Laufzeit ist nicht entscheidbar , und vice versa.$N$$N$$L$$N$$f(n)$$N$$1$$M$$N$$M$$N$$N$$L$$N$

$n^{i+1}$$n^i$$i$$\neq$

Nachdem ich mehr über das Thema nachgedacht habe, denke ich, dass ich eine (mögliche) Antwort für Ihr Q4 gefunden habe .

• Frage 4: Welche anderen Attribute von P (außer Laufzeitexponenten) sind derzeit als unentscheidbar bekannt? Für welche Attribute von$P$$P$

Ich habe eine Variation des Satzes von Rice bewiesen , die Ihre Frage für die meisten Eigenschaften beantwortet. Ich werde versuchen, mich diesmal klarer zu erklären (die Antwort von Travis Service war viel klarer und allgemeiner als meine vorherige Antwort).

$E$$E$$O(f(n))$$f(n)=\Omega(n \log n)$$f(n)=\Omega(g(n))$$g(n)$

$f(n)$$P$

$S$$S$$S$$S \subseteq R$$S$

$P$$S \subseteq P$

$S$

$P(E)$$E$$P$$E$$S$$E$$(A, i)$$A$$i$$A$$A$$i$

$S$$s \in S$$S$$C$$s$$C$$g(n)$

function H(x)
h := simulate A on i for |X| steps and return whether it halted
if h == 'halted' then
    reject
else
    if C(x) accepts then
        accept
    else
        reject
    fi
fi

$O(n \log n)$

$P(H)$$A$$i$$A$$i$$t$$H$$X$$|X| \geq t$$H$$S$$P(H)$

$A$$i$$C$$s \in S$$P(H)$$P(H)$

Ich kann dein Q1 negativ beantworten und damit auch Q2 und Q3 negativ beantworten . Bei Q4 oder Q5 bin ich mir allerdings nicht sicher .

• $L$$P$

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

$T$$k$$T$$O(n^k)$$M$$k$$T$$T$$k$ $T$

$L$$P$$T$$O(n^k)$$k$$L$$M$$k$$T$

$L$$P$$T$$L$$T$

$L$$P$$M$$T$$L$$T$$L$

$L$$P$$L$$O(n^k)$$M$$n$$n^{k+1}$$n^{k+2}$$L$

$M$$P$$L$$L$$k$$M$

Diese Art des Denkens über Unentscheidbarkeit ist anscheinend weit verbreitet. Ich erinnere mich an einen (Blog-?) Beitrag zu einem sehr ähnlichen Thema: Die Frage lautete: "Ist es entscheidbar, ob Pi eine 'letzte Null' hat?" Dezimalrepräsentation, wenn Sie diese Repräsentation weit genug senken. Wir wissen derzeit nicht, ob dies der Fall ist. Wir könnten es nicht einmal jemals beweisen können, oder es könnte sogar unabhängig von unseren Axiomensystemen sein (und dadurch unbeweisbar). Da die Antwort entweder wahr oder falsch ist, entscheiden ein TM, das wahr zurückgibt, und ein TM, das falsch zurückgibt, in beiden Fällen über das Problem, und daher ist das Problem entscheidbar.

Ich werde sehen, ob ich diesen Beitrag irgendwo im Internet finde.

Bearbeiten:

Ich habe es auf Mathoverflow gefunden .