Wie ist das Problem des Handlungsreisenden in polynomialer Zeit überprüfbar?

Ich verstehe die Idee, dass das Entscheidungsproblem definiert ist als

Gibt es einen Pfad P, bei dem die Kosten niedriger als C sind?

und Sie können leicht überprüfen, ob dies der Fall ist, indem Sie einen Pfad überprüfen, den Sie erhalten.

Was ist jedoch, wenn es keinen Pfad gibt, der diesen Kriterien entspricht? Wie können Sie die Antwort "Nein" verifizieren, ohne das TSP-Problem für den besten Pfad zu lösen und herauszufinden, dass das beste Problem schlechtere Kosten verursacht als C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
quelle

Persönlich hatte ich nur gehört, dass die Klasse NP eine Mehrfachzeitüberprüfung bedeutet, aber nie die Einschränkung gesehen, dass dies nur die Überprüfung der Antworten mit "Ja, hier ist die Lösung" bedeutet. Es scheint intuitiv vorstellbar, dass Sie in der Lage sein müssen, jede Lösung in Poly-Time zu überprüfen.

wjmccann

Antworten:

NP ist die Klasse von Problemen, bei denen Sie "Ja" -Instanzen überprüfen können. Es wird keine Garantie gegeben, dass Sie "keine" Instanzen überprüfen können.

Die Klasse von Problemen, bei denen Sie "keine" Instanzen in der Polynomzeit verifizieren können, ist co-NP . Jede Sprache in co-NP ist die Ergänzung einer Sprache in NP und umgekehrt. Beispiele umfassen Dinge wie Nicht-3-Färbbarkeit. Das von Ihnen beschriebene Problem: "Gibt es keinen TSP-Pfad mit einer Länge von höchstens ?" ist auch in Co-NP $C$ : Wenn Sie die Doppelverneinung aufheben, ist eine "Nein" -Instanz für dieses Problem eine "Ja" -Instanz für TSP, und wir können diese in polynomieller Zeit überprüfen.

Es gibt einige Probleme, wie die ganzzahlige Faktorisierung und alle Probleme in P , von denen wir wissen, dass sie sowohl in NP als auch in co-NP auftreten . (Danke an user21820 für diesen Hinweis.)

Es ist nicht bekannt, ob NP und Co-NP die gleichen Probleme haben. Wenn sie identisch sind, können wir die TSP-Instanzen "yes" und "no" überprüfen. Wenn sie unterschiedlich sind, dann P $\,\neq\,$ NP , da wir wissen, dass P $\,=\,$ co-P (weil wir einfach die Antwort einer deterministischen Maschine negieren können, indem wir die Antwort auf das Komplementproblem geben).

David Richerby
quelle

Es kann erwähnenswert sein, dass wir einige Probleme kennen, die sowohl in NP als auch in coNP auftreten, aber nicht wissen, ob sie in P vorliegen oder nicht, wie die ganzzahlige Faktorisierung.

user21820

@ user21820 Ganzzahlfaktorisierung ist kein Entscheidungsproblem. Primalität ist ein Entscheidungsproblem und es war jahrelang bekannt, dass es sowohl im NP als auch im Co-NP ist . Schließlich wurde gezeigt, dass es auch in P ist . Ich weiß nicht, ob es noch Probleme gibt, von denen bekannt ist, dass sie sowohl im NP als auch im Co-NP auftreten, ohne dass nachgewiesen wurde, dass sie in P sind .

Kasperd

@kasperd: Es ist allgemein bekannt, dass die ganzzahlige Faktorisierung, wenn sie zu einem Entscheidungsproblem gemacht wird (Hat n einen Primfaktor kleiner als m?), sowohl in NP als auch in coNP erfolgt (beide Ja / Nein-Instanzen können in Polynomzeit über verifiziert werden) Der AKS-Primalitätstest wurde mit der Primfaktorisierung (als Zertifikat) durchgeführt, es wurde jedoch noch nicht gezeigt, dass er am

20.

@ user21820 Es gibt viel einfachere und schnellere Möglichkeiten, eine Faktorisierung zu überprüfen als AKS.

Kasperd

@kasperd: Ich wäre gespannt darauf. Um eine Faktorisierung zu verifizieren, benötigen Sie beispielsweise die Primfaktoren und für jeden Primfaktor einen Beweis, dass es sich um eine Primzahl handelt.

gnasher729

"Wie ist das Problem des Handlungsreisenden in polynomialer Zeit überprüfbar?"

Entweder so, wie Sie es beschreiben, oder es ist nicht bekannt, dass es so ist.

"Aber was ist, wenn es keinen Pfad gibt, der diesen Kriterien entspricht?"

In diesem Fall gibt die Maschine für alle NP-Maschinen für das Entscheidungsproblem Nein für alle Kandidatenzertifikate zurück.

"Wie würden Sie die Antwort" Nein "verifizieren, ohne das beste Pfad-TSP-Problem zu lösen, und herauszufinden, welches das beste ist, kostet weniger als C?"

Nun, man könnte einen interaktiven Beweis erhalten, dass es solche Pfade nicht gibt .

Es ist nicht bekannt, dass das von Ihnen beschriebene Problem, TSP, in coNP vorliegt . Es gibt also keine "NP-ähnliche" Methode, um zu überprüfen, ob es einen solchen Pfad gibt.

Juho
quelle