Bedeutet "Zweites X ist NP-vollständig" "X ist NP-vollständig"?

11

Das "zweite " -Problem ist das Problem, die Existenz einer anderen Lösung zu entscheiden, die sich von einer gegebenen Lösung für eine Probleminstanz unterscheidet.X

Für einige vollständige Probleme ist die zweite Lösungsversion N P- vollständig (Entscheidung über die Existenz einer anderen Lösung für das partielle lateinische Quadrat-Vervollständigungsproblem), während sie für andere entweder trivial ist (zweites NAE SAT) oder nicht N sein kann P- vollständig (Zweiter Hamilton-Zyklus in kubischen Graphen) unter weit verbreiteter Komplexitätsvermutung. Ich interessiere mich für die entgegengesetzte Richtung.NPNPNP

Wir nehmen ein natürliches -Problem X an, bei dem es einen natürlichen effizienten Verifizierer gibt, der eine natürliche interessante Beziehung ( x , c ) verifiziert , wobei x eine Eingabeinstanz ist und c ein kurzer Zeuge der Zugehörigkeit von x zu X ist . Alle Zeugen sind für den Prüfer nicht zu unterscheiden. Die Gültigkeit von Zeugen muss durch Ausführen des natürlichen Prüfers entschieden werden, und es gibt keine Kenntnis von korrekten Zeugen (beide Beispiele in den Kommentaren sind per Definition Lösungen). NPX(x,c)xcxX

Bedeutet "Zweites ist NP-vollständig" " X ist NP-vollständig" für alle "natürlichen" Probleme X ?XXX

Mit anderen Worten, gibt es ein "natürliches" Problem bei dem diese Implikation fehlschlägt? X. Oder äquivalent,

Gibt es ein "natürliches" Problem in N P, von dem nicht bekannt ist, dass es N P- vollständig ist, aber sein zweites X- Problem ist N P- vollständig?XNPNPXNP

EDIT : Dank Marzios Kommentaren bin ich nicht an erfundenen Gegenbeispielen interessiert. Ich interessiere mich nur für natürliche und interessante Gegenbeispiele für NP-vollständige Probleme ähnlich den oben genannten. Eine akzeptable Antwort ist entweder ein Beweis für die obige Implikation oder ein Gegenbeispiel "Zweites X-Problem", das für das natürliche, interessante und bekannte N P- Problem X definiert ist .XNPX

EDIT 2 : Dank der fruchtbaren Diskussion mit David Richerby habe ich die Frage bearbeitet, um zu betonen, dass mein Interesse nur an natürlichen Problemen .X

EDIT 3 : Motivation: Erstens kann das Vorhandensein einer solchen Implikation die Vollständigkeitsnachweise vieler N P -Probleme vereinfachen . Zweitens verbindet die Existenz der Implikation die Komplexität der Entscheidung über die Eindeutigkeit der Lösung mit dem Problem der Entscheidung über die Existenz einer Lösung für N P -Probleme.NPNPNP

Mohammad Al-Turkistany
quelle
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Bjørn Kjos-Hanssen
Ihre EDIT 3 und EDIT 1 scheinen nicht in einer Reihe zu stehen. Wenn Sie möchten, dass dies ein allgemeines Ergebnis ist, das zur Vereinfachung der NP-Vollständigkeitsnachweise nützlich ist, können Sie nicht auch sagen, dass Sie nur "nicht erfundene" Gegenbeispiele möchten. Es wäre auch nützlich, eine Definition von "natürlich / interessant" zu haben, die nicht auf persönlicher Meinung basiert.
Chris Jefferson

Antworten:

9

Nein,

Betrachten Sie das Problem "Finden Sie eine Teilmenge einer Menge von ganzen Zahlen S, die sich zu 0 summiert".

Dieses Problem ist trivial, da man den leeren Satz zurückgeben kann.

Das Finden einer zweiten Lösung nach dem Zurückgeben der leeren Menge ist jedoch das bekannte Teilmengen-Summenproblem, von dem bekannt ist, dass es NP-vollständig ist.

Chris Jefferson
quelle
4
Dies spielt keine Rolle, es sei denn, Sie können ein "unnatürliches" Problem definieren. Menschen definieren Hunderte von Varianten von Problemen wie Teilmengen und SAT.
Chris Jefferson
5
@Mohammad: Hier ist ein weiteres Gegenbeispiel; Ich überlasse es Ihnen zu entscheiden, ob es natürlich ist oder nicht: Ein Bimatrix-Spiel hat immer mindestens ein Nash-Gleichgewicht und es ist NP-schwer zu entscheiden, ob ein Bimatrix-Spiel mehr als ein Nash-Gleichgewicht hat [Gilboa und Zemel, GEB 1989]. . Die Konstruktion nimmt eine SAT-Formel f und erzeugt ein Spiel mit einem bestimmten Nash-Gleichgewicht bekannter Form, das immer existiert, so dass das Spiel ein zweites Gleichgewicht hat, wenn die Formel f erfüllt werden kann.
Rahul Savani
4
f:{0,1,2,,2n1}{0,1}f(0)=0f(2n1)=1kf(k)=0f(k+1)=1
3
NP complete bedeutet nicht, dass alle Instanzen schwierig sind, nur einige. Es gibt viele triviale Instanzen von Teilmengen (alle Probleme, die zum Beispiel 1 und - 1 enthalten) und viele einfache SAT-Probleme (zum Beispiel 2 SAT), aber SAT als Ganzes ist immer noch NP-vollständig.
Chris Jefferson
3
Die Antwort muss eine Teilmenge der Menge von ganzen Zahlen S sein. {} Ist eine Teilmenge von S, da die leere Menge eine Teilmenge aller Mengen ist. {ϕ} ist keine Teilmenge von S, da S nicht ϕ enthält
Chris Jefferson
0

ASPNP

NP

Mohammad Al-Turkistany
quelle
1
Ihr Problem war, ob die NP-Vollständigkeit der zweiten Lösung die NP-Vollständigkeit impliziert. Was sie zeigen, ist schwächer, sie erfordern ASP-Vollständigkeit, da NP-Vollständigkeit nicht ausreicht, wie in den Kommentaren zu Ihrer Frage ausgeführt.
Domotorp
2
Wenn jemand dies liest, ist diese Antwort falsch. Es ist leicht, ein Problem zu erzeugen, bei dem Second X NP-vollständig ist, X jedoch nicht NP-vollständig ist. Zum Beispiel (wie in den obigen Kommentaren erläutert) ist das Problem, eine Teilmenge einer Menge von ganzen Zahlen zu finden, die sich zu 0 summiert, Second X NP-complete, da es NP-complete ist, sobald wir die einfache erste Lösung der leeren Menge ablehnen .
Chris Jefferson
2
ΠΠ[2]ΠΠΠ[2]Π[2]Π
Sasho Nikolov
4
Es ist etwas seltsam für jemanden, eine Frage zu stellen, sie zu beantworten und sie dann zu akzeptieren, während die Diskussion weitergeht.
Chandra Chekuri
1
@ MohammadAl-Turkistany Mein Kommentar war, dass Ihre Antwort die Logik rückwärts gebracht zu haben scheint und Ihre eigene Frage nicht beantwortet. Ich habe nichts über Chris 'Beispiel gesagt (was für mich gut aussieht, aber ich möchte in den Kommentaren nicht auf dieses Argument eingehen).
Sasho Nikolov