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

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 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 vollständig (Zweiter Hamilton-Zyklus in kubischen Graphen) unter weit verbreiteter Komplexitätsvermutung. Ich interessiere mich für die entgegengesetzte Richtung. $NP$ $NP$ $NP$

Wir nehmen ein natürliches -Problem bei dem es einen natürlichen effizienten Verifizierer gibt, der eine natürliche interessante Beziehung verifiziert wobei eine Eingabeinstanz ist und ein kurzer Zeuge der Zugehörigkeit von zu . 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). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

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

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 nicht bekannt ist, dass es vollständig ist, aber sein zweites Problem ist vollständig? $X$ $NP$ $NP$ $X$ $NP$

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 Problem . $X$ $NP$ $X$

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 -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 -Probleme. $NP$ $NP$ $NP$

cc.complexity-theory unique-solution 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:

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

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

@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

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

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

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

$ASP$ $NP$

$NP$

Mohammad Al-Turkistany
quelle

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

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

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Sasho Nikolov

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

@ 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