Werden NP-vollständige Sätze nur dann aus zwei anderen Sätzen gebildet, wenn mindestens einer NP-hart ist?

Diese Frage ist eine Art Umkehrung zu einer früheren Frage zu Mengen, die aus Mengenoperationen für NP-vollständige Mengen gebildet wurden:

Wenn die Menge, die sich aus der Vereinigung, dem Schnittpunkt oder dem kartesischen Produkt zweier entscheidbarer Mengen und ergibt, NP-vollständig ist, ist mindestens eine von notwendigerweise NP-hart? Ich weiß, dass sie nicht beide in P sein können (unter der Annahme von P! = NP), da P unter diesen Mengenoperationen geschlossen ist. Ich weiß auch, dass die Bedingungen "entscheidbar" und "NP-hart" notwendig sind, denn wenn wir einen NP-vollständigen Satz und einen anderen Satz außerhalb von NP betrachten (ob nur NP-hart oder unentscheidbar), können wir zwei neue bilden NP-harte Sätze nicht in NP, deren Schnittpunkt NP-vollständig ist. Zum Beispiel: und . Ich weiß jedoch nicht, wie ich danach vorgehen soll. $L_1$ $L_2$ $L_1, L_2$ $L$ $B$ $L_1:= 01L \cup 11B$ $L_2:= 01L \cup 00B$

Ich denke, dass der Fall der Vereinigung möglicherweise nicht wahr ist, da wir eine NP-vollständige Menge und die Konstruktion in Ladners Theorem ausführen können, um eine Menge NPI zu erhalten, die eine Teilmenge von . Dann ist der ursprüngliche NP-vollständige Satz. Ich weiß jedoch nicht, ob noch in NPI oder NP-hard ist. Ich weiß nicht einmal, wo ich für den Fall der Kreuzung und des kartesischen Produkts anfangen soll. $A$ $B \in$ $A$ $B \cup (A \setminus B) = A$ $A \setminus B$

complexity-theory np-hard np np-intermediate Ari
quelle

Ein Problem in P kann NP-vollständig sein, wenn P = NP, was Ihre Behauptung "Sie können nicht beide in P sein" falsch macht.

Wojowu

@ Wojowu Danke, du bist richtig. Ich habe nur angenommen, dass verstanden wurde, dass diese ganze Frage auf der Prämisse basiert, dass P! = NP. Ansonsten ist es bedeutungslos / trivial, da wir dann NPC = P hätten. Ich werde die Frage bearbeiten.

Ari

@Ari, Eigentlich , auch wenn .

N P C \neq P

$NPC\not = P$

P = N P

$P=NP$

Tom van der Zanden

@ TomvanderZanden Wie ist das möglich? Wenn also P = NP ist, kann jedes Problem in NP in Polynomzeit einschließlich der Probleme in NPC gelöst werden.

N P C \subseteq N P

$NPC \subseteq NP$

Ari

@Ari Die leere Menge und die Menge aller Zeichenfolgen sind in , aber sie sind nicht vollständig. Sie können nichts auf die leere Menge (oder die Menge aller Zeichenfolgen) reduzieren, da es sich immer um eine Nein-Instanz (bzw. Ja-Instanz) handelt.

N P

$NP$

N P

$NP$

Tom van der Zanden

Antworten:

Der Schnittpunkt zweier nicht NP-harter Sprachen kann NP-hart sein. Beispiel: Die Lösungen einer 3SAT-Instanz sind der festgelegte Schnittpunkt der Lösungen einer HORN-3SAT-Instanz und einer ANTIHORN-3SAT-Instanz. Dies liegt daran, dass eine 3CNF-Klausel entweder eine Horn- oder eine Anti-Horn-Klausel sein muss und eine 3SAT-Instanz die Verbindung solcher Klauseln ist. 3SAT ist natürlich NP-vollständig; HORN-3SAT und ANTIHORN-3SAT sind beide in P.

Kyle Jones
quelle

Ich kann deinem Beispiel nicht folgen. Der Schnittpunkt von HORN-SAT und ANTIHORN-SAT ist eine ziemlich langweilige Sprache, die definitiv in P.

Yuval Filmus

HORN-3SAT kann auf viele Arten definiert werden. Eine Möglichkeit besteht darin, eine Codierung von HORN-3SAT-Instanzen zu korrigieren - jede Zeichenfolge codiert eine solche Instanz - und dann besteht HORN-3SAT aus den erfüllbaren Instanzen. Diese Codierung unterscheidet sich wahrscheinlich von der Codierung, die Sie für ANTIHORN-3SAT verwenden würden. Daher ist nicht klar, wie genau die Schnittpunktsprache lautet - definitiv nicht SAT.

Yuval Filmus

Eine andere Möglichkeit besteht darin, HORN-3SAT als die Sprache von 3SAT-Instanzen zu definieren, die (i) in Hornform, (ii) erfüllbar sind. Nun ist der Schnittpunkt von HORN-3SAT und ANTIHORN-3SAT sinnvoll: Er besteht aus allen 3SAT-Instanzen, die (i) sowohl in Horn- als auch in Anti-Horn-Form vorliegen, (ii) erfüllbar sind. Dies kann nur einfacher sein als HORN-3SAT und ANTIHORN-3SAT.

Yuval Filmus

Dies ist eine sehr seltsame Definition der Sprachschnittstelle, die sich von der hier gemeinten unterscheidet. Wenn und Sprachen sind (wie 3SAT), meinen wir mit ihrem Schnittpunkt .

L_{1}

$L_1$

L_{2}

$L_2$

L_{1} \cap L_{2}

$L_1 \cap L_2$

Yuval Filmus

@ KyleJones @ Yuval Ich denke, es könnte einige Verwirrung in Bezug auf Instanzen und Sprachen geben. Während jede Instanz von 3SAT sicherlich nur aus Horn-Klauseln und Anti-Horn-Klauseln besteht, ist es nicht so , dass die Sprache gleich oder alternativ da diese Mengen Instanzen haben, die jeweils nur aus Horn-Klauseln oder Anti-Horn-Klauseln bestehen, während jede Instanz von 3SAT eine Mischung dieser beiden Arten von Klauseln haben kann.

3 S A T

$\mathsf{3SAT}$

H O R N 3 S A T \cap A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cap\mathsf{ANTIHORN3SAT}$

H O R N 3 S A T \cup A N T I H O R N 3 S A T

$\mathsf{HORN3SAT}\cup\mathsf{ANTIHORN3SAT}$

Ari