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

10

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 2 L 1 , L 2 L B L 1 : = 01 L 11 B L 2 : = 01 L 00 B.L1L2L1,L2LBL1:=01L11BL2:=01L00B

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.B A B ( A B ) = A A B.ABAB(AB)=AAB

Ari
quelle
1
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
1
@ 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 . P = N P.NPCPP=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. NPCNP
Ari
2
@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.NPNP
Tom van der Zanden

Antworten:

1

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
5
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
1
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
1
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
4
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 . L1L2L1L2
Yuval Filmus
3
@ 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.3SATHORN3SATANTIHORN3SATHORN3SATANTIHORN3SAT
Ari