Warum ist dieses Problem in NP nicht unentscheidbar?

25

Offensichtlich gibt es in NP keine unentscheidbaren Probleme. Laut Wikipedia jedoch :

NP ist die Menge aller Entscheidungsprobleme, für die die Fälle, in denen die Antwort "ja" lautet, Beweise haben, die in Polynomzeit durch eine deterministische Turing-Maschine überprüfbar sind.

[...]

Ein Problem liegt nur dann in NP vor, wenn ein Verifizierer für das Problem existiert, der in Polynomzeit ausgeführt wird.

Betrachten Sie nun das folgende Problem:

Gibt es bei einer diophantinischen Gleichung ganzzahlige Lösungen?

Bei einer gegebenen Lösung ist es einfach, in polynomieller Zeit zu überprüfen, ob es sich tatsächlich um eine Lösung handelt: Geben Sie einfach die Zahlen in die Gleichung ein. Das Problem liegt also in NP. Es ist jedoch bekannt, dass die Lösung dieses Problems unentscheidbar ist !

(In ähnlicher Weise scheint es, dass das Stopp-Problem in NP liegen sollte, da die "Ja" -Lösung von "dieses Programm stoppt im N-ten Schritt" in N Schritten verifiziert werden kann.)

Offensichtlich stimmt etwas nicht mit meinem Verständnis, aber was ist es?

BlueRaja - Danny Pflughoeft
quelle
1. Denken Sie daran, dass die von Ihnen angegebene Definition für Entscheidungsprobleme gilt. 2. Bezüglich Ihres diophantinischen Beispiels behaupten Sie nicht, dass es für jedes System ein Polynom gibt, das an die Größe der Lösungen gebunden ist, oder?
Dmitri
@ Dmitri: Ähm, ja, das behaupte ich. Die Größe der Lösung entspricht genau der Größe des Problems. Wenn N Unbekannte vorhanden sind, enthält die Lösung N ganze Zahlen. Und dies ist ein Entscheidungsproblem - die ganzzahlige Lösung (die zur Überprüfung des "Ja" -Falls benötigt wird) wäre das Zertifikat .
BlueRaja - Danny Pflughoeft
19
Die Frage ist, wie groß die Intgerers sind
Artem Kaznatcheev
10
@ BlueRaja-DannyPflughoeft Wenn du ein unendliches Alphabet hast, um deine ganzen Zahlen zu kodieren, dann bist du nicht mehr in der Standardeinstellung der Komplexitätstheorie. Bei einem endlichen Alphabet wächst die Größe der Codierung mit dem Wert einer ganzen Zahl.
Dmitri Chubarov
Eine Lösung für das Halteproblem würde nur "Ja" zurückgeben, ohne einen Hinweis darauf zu geben, wie viele Schritte zur Überprüfung simuliert werden müssen.
RemcoGerlich

Antworten:

10

Eine äquivalente Definition von NP ist, dass es aus allen Problemen besteht, die in der Polynomzeit durch eine nicht deterministische Turing-Maschine entscheidbar (nicht nur überprüfbar) sind. Es ist bekannt, dass NTMs nicht leistungsfähiger sind als TMs in dem Sinne, dass die Menge der von NTMs entscheidbaren Probleme mit der Menge der von TMs entscheidbaren Probleme identisch ist, so dass es nach dieser Definition keine nicht entscheidbaren Probleme in NP geben kann.

Um zu demonstrieren, dass die beiden Definitionen von NP äquivalent sind, können Sie bei Vorhandensein eines deterministischen Verifizierers nachweisen, dass ein nicht deterministischer Entscheider existiert, und umgekehrt.

Angenommen, Sie haben einen deterministischen Polynomprüfer. Dann gibt es auch eine Maschine, die ein Zertifikat mit einer durch das Polynom begrenzten Länge entsprechend der für dieses Problem / diesen Prüfer gebundenen Zertifikatgröße nicht deterministisch errät und dann den Prüfer ausführt. Da das Alphabet endlich ist, ist das Zertifikat für eine bestimmte Eingabe endlich (und höchstens polynomisch in der Größe der Eingabe), und der Prüfer wird in polynomischer Zeit ausgeführt. Die Maschine hält in allen Zweigen für alle Eingaben an und läuft in deterministische) Polynomzeit. Somit gibt es für jeden deterministischen Verifizierer einen nicht deterministischen Entscheider.

Wenn Sie einen nicht deterministischen Entscheider haben, können Sie für jede akzeptierende Berechnung den Pfad der Entscheidungen aufzeichnen, die der Entscheider getroffen hat, um den Akzeptanzstatus zu erreichen. Da der Entscheider in Polynomzeit läuft, hat dieser Pfad höchstens eine polynomielle Länge. Und es ist einfach für eine deterministische TM zu bestätigen , dass ein solcher Pfad ist ein gültiger Pfad durch eine NTM auf einen Zustand annehmen, so solche Pfade bilden Zertifikate für ein Polynom Verifizierer für das Problem. Somit gibt es für jeden nicht deterministischen Entscheider einen deterministischen Verifizierer.

Somit kann jede unentscheidbar Problem kann nicht einen Prüfer haben , dass die Arbeiten auf Zertifikate von Polynom Größe (sonst die Existenz der Verifizierer die Existenz eines Entscheiders bedeuten würde).


Wenn Sie behaupten, dass ein Verifizierer für das Problem des Anhaltens vorhanden ist, handelt es sich bei dem Zertifikat, von dem Sie sprechen, um eine Codierung von (TM, I, N), wobei das TM bei Eingabe I in N Schritten angehalten wird. Dies kann in der Tat in N Schritten überprüft werden, aber die Größe des Zertifikats ist nicht polynomiell in Bezug auf die Größe der (TM, I) -Eingabe für das ursprüngliche Problem (das Halteproblem). N kann beliebig groß sein (unabhängig von der Codierung). Wenn Sie versuchen, einen solchen Prüfer in einen nicht deterministischen Entscheider umzuwandeln, erhalten Sie eine interessante Maschine. Sie sollten in der Lage sein, dies zu beweisen, wenn Sie mit (TM, I) für ein TM arbeiten, das dies nicht tutBei Eingabe anhalten I gibt es keine nicht anhaltenden Pfade durch die Maschine, aber für jeden Pfad, der zu einem anhaltenden Zustand führt, gibt es immer einen weiteren längeren Pfad (entsprechend einer Schätzung eines größeren N), und daher gibt es keine endliche Grenze seine Ausführungszeit. Dies liegt im Wesentlichen daran, dass es einen unendlichen Raum gibt, der durch die anfängliche nicht deterministische Vermutung erkundet werden muss. Das Konvertieren eines solchen NTM in ein deterministisches TM führt zu einem dieser Computer, der bei einigen Eingaben weder eine Schleife ausführt noch anhält. Tatsächlich gibt es kein NTM, das über das Problem des Anhaltens entscheiden kann, und daher gibt es keinen Verifizierer, der mit Zertifikaten mit einer begrenzten Größe arbeitet.

Ich kenne mich mit diophantinischen Gleichungen nicht so gut aus, aber es sieht so aus, als würde das gleiche Problem auch für Ihre Argumentation gelten.

Aus diesem Grund fällt es mir leichter, über die NTM-Definition von NP nachzudenken. Es gibt Prüfer für Probleme, die nicht entschieden werden können (nur nicht für Zertifikate, deren Polynomgröße an die Größe der Eingabe des ursprünglichen Problems gebunden ist). Tatsächlich kann jedes TM, das eine Sprache erkennt , aber nicht entscheidet , leicht in einen Prüfer für dieselbe Sprache umgewandelt werden.

Wenn Sie an Verifizierer denken, müssen Sie die Zeitgrenzen in Bezug auf die Größe der ursprünglichen Problemeingabe angeben, nicht in Bezug auf die Zertifikatgröße. Sie können die Größe von Zertifikaten beliebig erhöhen, so dass der Prüfer in Bezug auf die Größe des Zertifikats in einer kürzeren Zeit ausgeführt wird.

Ben
quelle
26

Ich denke, Sie haben falsch verstanden, was es bedeutet, eine diophantische Gleichung und Matiyasevichs Unentscheidbarkeitssatz zu lösen .

Matiyasevich bewies , dass für jeden RE Satz befindet sich eine diophentine Gleichung f ( n , x 1 , . . . , X k ) , so dass n S nur dann , wenn es vorhanden ist ganzzahligen Koeffizienten x 1 , .., x k , so dass f ( n , x 1 , . . . , x k ) = 0Sf(n;x1,...,xk)nSx1xkf(n;x1,...,xk)=0. Insbesondere ist das Halteproblem eine typische RE-Menge, und daher ist das Lösen des obigen Problems nicht zu entscheiden.

Beachten Sie, dass sind nicht in der Größe beschränkt und können im Allgemeinen beliebig groß sein, so dass in diesem Problem kein Zertifikat mit "polynomialer Größe" erkennbar ist.x1,...xk

Zu erweitern: die ganzen Zahlen müssen binär geschrieben werden, um ein Zertifikat zu sein. Da diese Ganzzahlen beliebig groß sein können (unabhängig von n ), haben wir festgestellt, dass das Zertifikat in log n oder wichtiger, nicht polynomiell ist und nicht an eine berechenbare Funktion gebunden ist.x1,...,xknLogn

Jedes Problem in jedoch ein Zertifikat, das durch ein Polynom p ( N ) begrenzt ist (wobei N die Größe der Eingabe ist). So N P Fragen sind triviale entscheidbar, da man alle möglichen Bitkette bis Länge aufzählen kann p ( N ) , und wenn keiner von ihnen die Eingabe, return false zertifizieren. Wenn dies der Fall ist, wird true zurückgegeben.NPp(N)NNPp(N)

Artem Kaznatcheev
quelle
Natürlich verstehe ich, was es heißt, "eine diophantische Gleichung zu lösen" - Sie finden Zahlen, die die Gleichung erfüllen. Ich verstehe nicht, warum Matiyasevichs Unentscheidbarkeitssatz oder rekursiv aufzählbare Mengen in die Diskussion einbezogen werden müssen. Aber ich denke, der letzte Absatz könnte es erklären ...
BlueRaja - Danny Pflughoeft
1
Okay, diese neue Bearbeitung erklärt es - das erklärt auch, warum das Problem des Anhaltens nicht in NP vorliegt, da die Schritte, die zum Anhalten erforderlich sind, beliebig groß sein können. Vielen Dank!
BlueRaja - Danny Pflughoeft
Mein Vorschlag war, die ersten beiden Absätze zu entfernen. Die ersten beiden Absätze erklären, warum Hilberts 10. Problem unentscheidbar ist, was für die Frage völlig tangential ist. Sie lenken nur vom Rest der Antwort ab (was ansonsten eine großartige Antwort ist!) .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft wenn der erste Absatz dich beleidigt hat, dann kann ich ihn entfernen (obwohl du gefragt hast "Was ist mit meinem Verständnis falsch ?"). Der zweite Absatz ist notwendig, um das Problem formeller zu formulieren, da Sie nicht in Ihrer Frage stehen.
Artem Kaznatcheev
3
@ BlueRaja-DannyPflughoeft Am besten ist es, wenn Fragen und Antworten in sich geschlossen sind. Mein zweiter Absatz beschreibt das Problem und erklärt, was es bedeutet, dass dieses Problem unentscheidbar ist. Mein dritter Absatz gibt die schnelle Antwort. Mein 4. und 5. Absatz gehen ausführlicher darauf ein. Soweit ich das beurteilen kann, sind alle Absätze notwendig.
Artem Kaznatcheev
8

Sie sollten bis zur formalen Definition gescrollt haben :

LpqM

  • xMp(|x|)(x,y)
  • xLyq(|x|)M(x,y)=1
  • xLyq(|x|)M(x,y)=0

Das heißt, ein Prüfer muss auch an Nichtlösungen arbeiten. Irgendwo dort drin scheitern unentscheidbare Probleme (in Ihrem Fall ist die Längenbeschränkung von Lösungskandidaten wahrscheinlich nicht erfüllt), wie aus der (im Sinne der Berechenbarkeit) klareren Definition hervorgeht :

NP ist die Menge von Entscheidungsproblemen, die von einer nicht deterministischen Turing-Maschine, die in Polynomzeit läuft, entschieden werden können.

Raphael
quelle
"Ein Verifizierer muss auch bei Nicht-Lösungen funktionieren" - wenn Sie sagen, dass der Verifizierer bei Nicht-Lösungen fehlschlagen muss, ist dies bereits der Fall. Wenn Sie behaupten, dass der Prüfer in der Lage sein muss, "keine" Antworten zu prüfen, ist das falsch - das wäre Co-NP . Die zweite Definition ist mir bereits bekannt, aber ich war verwirrt darüber, wie sie mit der ersten vergleichbar sein könnte, da die eine Definition das Problem in der Frage zuzugeben scheint, während die andere das nicht zulässt.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Meine Beobachtung ist: Prüfer müssen in der Lage sein, Nichtlösungen zu widerlegen. Wenn Sie sich dessen bewusst sind, bearbeiten Sie Ihre Frage entsprechend. es lässt dich ganz unerkannt aussehen.
Raphael
Es ist trivial offensichtlich, dass der Prüfer bereits Nicht-Lösungen ablehnt: Geben Sie einfach die Zahlen in die Gleichung ein und prüfen Sie, ob sie gültig sind. Ich verstehe leider nicht, worauf du hinaus willst.
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPlughoeft: Die von Ihnen angegebene "Definition" gibt dieses Verhalten nicht an.
Raphael
-1

Ich versuche mehr Details für meine obige Antwort anzugeben.

Tatsächlich ist diese Frage ein Dilemma.

Einerseits ist das Diophantine Equation Problem (DEP) nach Matiyesevichs Theorem unentscheidbar (Matiyesevichs Theorem beantwortet Hilberts zehntes Problem, und Turing's Halting-Problem beantwortet die Verallgemeinerung von Hilberts zehntem Problem, dh das Entscheidungsproblem); Andererseits gibt es in NP kein unentscheidbares Problem gemäß der Definition von NP (entscheidbar und überprüfbar).

Das heißt, entweder DEP ist nicht in NP oder DEP ist in NP. Beide betreffen die Definition von NP.

Wenn DEP nicht in NP ist, bedeutet dies, dass Probleme in NP (NDTM = NonDeterminstic Turing Machine) entscheidbar und überprüfbar sind, dh, wir akzeptieren P = NP (NDTM).

Wenn DEP in NP ist, dann enthält NP (NTM = Non Turing Machine) entscheidbare und unentscheidbare, offensichtlich entscheidbare ist überprüfbar, daher ist das Problem, ob nicht entscheidbare überprüfbar ist? Tatsächlich ist das das berühmte Problem von P gegen NP. Unentscheidbar ist sicherlich nicht überprüfbar, daher entspricht NP NTM (Non Turing Machine) anstelle von NDTM (NonDeterminstic Turing Machine).

Unter der Prämisse, dass DEP in NP (NTM) vorkommt, glauben wir, dass NP (NTM) ein nicht deterministisches Problem ist (unentscheidbar), und die derzeitige Definition von NP (NDTM, entscheidbar und überprüfbar) hat diesen Nicht-Determinismus (unentscheidbar) verloren Wir denken, dass es in Frage gestellt werden muss.

Yu Li
quelle
1
Nein, die Unentscheidbarkeit von DEP (Hilberts zehntes Problem) wurde erst 1970 von Matiyesevich aufgezeigt. Das Entscheidungsproblem ist nicht Hilberts zehntes Problem; betrifft die Gültigkeit von Formeln der Logik erster Ordnung. Und wieder einmal ist das P vs. NP- Problem absolut kein Problem, ob unentscheidbare Probleme überprüfbar sind.
David Richerby
1
Wenn Sie weitere Details angeben möchten, sollten Sie Ihren ursprünglichen Beitrag bearbeiten.
Tom van der Zanden
@DavidRicherby Beachten Sie, dass die Antwort von Ben: «Die Menge der von NTMs entscheidbaren Probleme ist identisch mit der Menge der von TMs entscheidbaren Probleme». In diesem Sinne denke ich, dass die Definition von NP P mit NP verwechselt und zu P = NP (NDTM) führt. Wenn diese Definition in Frage gestellt werden muss, müssen auch andere aus dieser Definition abgeleitete Schlussfolgerungen in Frage gestellt werden, wie die Äquivalenz eines deterministischen Verifizierers und eines nicht deterministischen Entscheiders.
Yu Li
@YuLi "führt zu P = NP (NDTM)." Ich habe keine Ahnung, was du damit meinst. Ich sehe auch nicht die Relevanz, darauf hinzuweisen, dass TMs und NTMs dieselbe Sprache wählen. Wenn sie nicht die gleichen Sprachen wählen würden, wären NTMs ein völlig unzumutbares Rechenmodell, und es ist schwer vorstellbar, dass es uns egal ist, was sie in polynomieller Zeit berechnen können. In der Komplexitätstheorie nehmen wir eine differenziertere Sichtweise und fragen nach den erforderlichen Rechenressourcen, und die Definition von NP verwirrt das überhaupt nicht.
David Richerby
@DavidRicherby Danke, ich habe meine Antwort entsprechend Ihrer Bemerkung geändert, um den Zusammenhang zwischen dem Entscheidungsproblem und Hilberts zehntem Problem zu verdeutlichen. Bezüglich der Frage nach der aktuellen Definition von NP ist es schwierig, in mehreren Worten zu diskutieren. Das Ziel meiner Antwort ist es, einige Überlegungen zu diesem grundlegenden Thema anzustellen,…
Yu Li
-2

Wir glauben, dass das Dilemma, das Sie in Bezug auf die diophantinische Gleichung aufgeworfen haben, sehr bedeutsam ist, da es etwas Auffälliges in der aktuellen Definition von NP aufdeckt: - Ein Problem wird in NP angegeben, wenn und nur wenn es einen Prüfer für das Problem gibt, das im Polynom ausgeführt wird Zeit.

Bezüglich der Definition von NP kann auf die 60er Jahre zurückgegriffen werden, in denen eine große Anzahl von anwendbaren und signifikanten Problemen entdeckt wurde, für die keine Polynomalgorithmen gefunden werden konnten, um diese Probleme anhand der in der Polynomzeit lösbaren Probleme zu erkennen (P) wurde das Konzept von NP herausgestellt.

Die derzeitige Definition von NP, die als in Polynomzeit überprüfbar definiert ist, verwechselt NP jedoch mit P, da ein Problem in P auch in Polynomzeit überprüfbar ist. Mit anderen Worten, eine solche Definition führt zum Verlust des Wesens von NP, «Nichtdeterminismus». Infolgedessen führt dies zu schwerwiegenden Unklarheiten beim Verständnis von NP, beispielsweise Ihrem Dilemma: Das Problem der diophantinischen Gleichung ist von Natur aus nicht zu entscheiden. aber nach der Definition von NP ist es entscheidend,…

Unserer Meinung nach liegt die Schwierigkeit bei der Lösung von «P versus NP» zunächst auf der Erkenntnisebene. Wenn wir also einen Einblick in «P versus NP» erhalten möchten, müssen wir uns zunächst fragen: Was ist NP?

Yu Li
quelle
4
Dies scheint ein Meinungsbeitrag über die Definition von NP zu sein , keine Antwort auf die Frage. Die Definition von NP ist in Ordnung. Es verwechselt P nicht mit NP ; vielmehr wird anerkannt, dass P eine Teilmenge von ist NP ist . Für mich wäre es sehr unnatürlich, wenn P keine Teilmenge von NP wäre . NP ist eine Klasse von Problemen, die innerhalb bestimmter Ressourcengrenzen gelöst werden können. Dazu gehört zwangsläufig eine ganze Reihe einfacher Probleme ( P ), die gelöst werden können, ohne an die Grenze der verfügbaren Ressourcen heranzukommen.
David Richerby
@DavidRicherby P und NP haben die gemeinsame Eigenschaft "Zertifikat in polynomieller Zeit überprüfbar", aber diese Eigenschaft ist nicht die Essenz von NP. Wenn diese Eigenschaft verwendet wird, um NP zu definieren, ist P eine Teilmenge von NP und NP hat P als seine Teilmenge (entscheidbar) und sich selbst (unentscheidbar). Daher würde man sich fragen, ob NP entscheidbar oder unentscheidbar ist. Genau wie das obige Dilemma: Ist die diophantinische Gleichung unentscheidbar oder entscheidbar? Meine Antwort ist also, vorzuschlagen, dieses Dilemma aus der Sicht der Definition von NP zu untersuchen: überprüfbar, unentscheidbar ist nicht überprüfbar!
Yu Li
Probleme in NP sind per Definition entscheidbar: NP ist die Klasse von Problemen , die von nicht deterministischen Turing-Maschinen entschieden werden. Es ist leicht zu beweisen, dass dies genau die gleichen Probleme sind, bei denen Zertifikate mit polynomieller Länge in polynomieller Zeit verifiziert werden können. Wenn Sie befürchten, dass Probleme in NP nicht entschieden werden können, haben Sie etwas falsch verstanden.
David Richerby
Ja, ich mache mir Sorgen, dass Probleme in NP möglicherweise nicht entschieden werden können. Sie sprechen von der Äquivalenz der beiden Definitionen von NP: NP ist die Klasse von Problemen, die von nichtdeterministischen Turing-Maschinen entschieden werden; NP ist die Klasse von Problemen, bei denen polynomielle Längenzertifikate in polynomieller Zeit verifiziert werden. Ich bezweifle diese Äquivalenz, weil es zum einen um die Existenz eines Algorithmus zur Lösung eines Problems und zum anderen um die Existenz einer Lösung für ein Problem geht. Das Dilemma der Diophantine Equation hängt möglicherweise direkt mit dieser Äquivalenz zusammen (siehe nähere Einzelheiten meines Arguments: arxiv.org/abs/1501.01906 ).
Yu Li
2
@YuLi Die Äquivalenz der beiden Definitionen von NP ist so einfach, dass sie in Komplexitätstheorieklassen unterrichtet wird. Ich empfehle, nicht auf ArXiv hochzuladen, wenn Sie die Grundlagen des Feldes nicht verstehen.
David Richerby