Poly-Zeit-Obermenge von NP-vollständiger Sprache mit unendlich vielen davon ausgeschlossenen Zeichenketten

14

Gibt es für jede beliebige NP-vollständige Sprache immer eine Polyzeit-Obermenge, deren Komplement ebenfalls unendlich ist?

Unter /cs//q/50123/42961 wurde eine triviale Version angefragt, die keine unendliche Ergänzung der Obermenge vorsieht

Für die Zwecke dieser Frage, können Sie davon ausgehen , dass . Wie Vor erklärte, ist die Antwort "Nein" , wenn P = N P ist. (Wenn P = N P , dann ist X = { x x N +x > 1 } NP-vollständig. Es gibt eindeutig keine Obermenge von X, die unendlich ist und ein unendliches Komplement hat, wie das Komplement von X nur hat ein einzelnes Element.) Somit können wir uns auf den Fall P N P konzentrieren .PNPP=NPP=NPX={xxN+x>1}XXPNP

ARi
quelle
5
Wenn dann ist X = { x x N +x > 1 } NP-vollständig. Es ist klar, dass es keine Obermenge von X gibt, die unendlich ist und ein unendliches Komplement hat (beachte, dass ˉ X = { 1 } ). So können Sie „Fokus“ auf das, was passiert , wenn P N P . P=NPX={xxN+x>1}XX¯={1}PNP
Marzio De Biasi
3
Wie über die relativierten Version: Gibt es ein Orakel st alle co-NP A - Sets sind P A - Immun. AAA
Lance Fortnow
@LanceFortnow ... oder für eine vollständige Sprache in einer bestimmten. Komplexitätsklasse, gibt es immer eine nicht triviale Obermenge einer geringeren Komplexität.
ARi

Antworten:

10

Jede -komplette Menge enthält eine unendliche Teilmenge in P unter der Annahme, dasscoNPP

  • Pseudozufallsgeneratoren existieren und
  • Es gibt sichere Einweg-Permutationen.

Mit anderen Worten : unter der Annahme, dass diese beiden Vermutungen wahr sind, nicht ist -komplette Satz P- immun . Wie in den Kommentaren von Lance ausgeführt, wird dies durch Satz 4.4 von impliziertcoNP

(Kaveh hat bereits gezeigt , dass Ihre Frage äquivalent ist , ob jeder -komplette Sätze enthält eine unendliche P Teilmenge. In anderer Sprache, dies zu sagen , dass keine c o N P -komplette Satz ist „ P - Immun.“ Diese ist die Sprache, die im oben zitierten Theorem verwendet wird.)coNPPcoNPP

Joshua Grochow
quelle
ECCC Draft
Kaveh
Durch starke Hardcore-Funktionen (und Iteration ) implizieren Einweg-Permutationen Pseudozufallsgeneratoren.
1
@ RickyDemer: Siehe Definitionen 4.1-4.3 in der zitierten Veröffentlichung. Wenn ich richtig verstehe, implizieren OWPs, was sie "Krypto-PRGs" nennen, aber nicht unbedingt, was sie "PRGs" in der Glasser-Pavan-Selman-Sengupta-Zeitung nennen. Für ihr Ergebnis brauchen sie (anscheinend) beide OWPs und das, was sie PRGs nennen.
Joshua Grochow
6
Kaveh zeigte nur, dass die Äquivalenz zu co-NP-vollständigen Mengen P-immun ist, aber die Schlussfolgerung von Satz 4.4 in Glasser et al., Dass alle NP-vollständigen Mengen eine längenerhöhende Reduktion aufweisen müssen, impliziert auch, dass es keine co-NP-vollständigen Mengen gibt. Komplette P-Immun-Sets.
Lance Fortnow
@JoshuaGrochow Danke ... aber gibt es Annahmen, die wir machen können, was wiederum die Nichtexistenz einer solchen Sprache impliziert. Ich war mehr an Szenarien interessiert, in denen es keine Poly-Time-Obermenge gibt
ARi
5

Interessante Frage. Die Aussage

Für jedes NP-vollständige gibt es U in P, so dass L U und U c unendlich sind.LULUUc

ist äquivalent zu:

für jeden NP-vollständig , Komplement von L enthält ein unendliches P - Set.LL

Das ist wiederum gleichbedeutend mit

jedes coNP-complete-set enthält ein unendliches p-set.

Das ist durch Symmetrie das gleiche wie

Jedes NP-Komplettset enthält ein unendliches P-Set.

Ich glaube nicht, dass die Antwort bekannt ist. Ich denke, natürliche NP-Komplett-Sets erfüllen diese Bedingung problemlos. Ich glaube nicht, dass wir Werkzeuge haben, um ein künstliches Set zu bauen, das die Aussage verfehlt. (Siehe Lances Kommentar unten)

Kaveh
quelle
Ihre ursprüngliche Aussage ist trivial wahr. (Sei U die volle Sprache.)
Es ist eine interessante Kette von Abzügen ... Könnten Sie ein Beispiel für eine vollständige NP-Sprache in dieser Hinsicht geben
ARi
3
Die Symmetrie ergibt keinen Sinn. Zum Beispiel hat jede ce-Menge eine unendliche berechenbare Teilmenge, aber es gibt ce-Mengen, die dies nicht tun.
Lance Fortnow