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

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 ist. (Wenn , dann ist NP-vollständig. Es gibt eindeutig keine Obermenge von die unendlich ist und ein unendliches Komplement hat, wie das Komplement von nur hat ein einzelnes Element.) Somit können wir uns auf den Fall . $P \ne NP$ $P = NP$ $P = NP$ $X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$ $X$ $X$ $P \ne NP$

cc.complexity-theory np-complete structural-complexity ARi
quelle

Wenn

dann ist

NP-vollständig. Es ist klar, dass es keine Obermenge von

die unendlich ist und ein unendliches Komplement hat (beachte, dass

). So können Sie „Fokus“ auf das, was passiert , wenn

P = N P

$P = NP$

X = {x ∣ x \in N^{+} \land x > 1}

$X = \{x \mid x \in \mathbb{N^+} \land x > 1\}$

X

$X$

\bar{X} = {1}

$\bar{X} = \{1\}$

P \neq N P

$P \neq NP$

Marzio De Biasi

Wie über die relativierten Version: Gibt es ein Orakel

st alle co-NP

- Sets sind P

- Immun.

A

$A$

^{A}

$^A$

^{A}

$^A$

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:

Jede -komplette Menge enthält eine unendliche Teilmenge in Annahme, dass $\mathsf{coNP}$ $\mathsf{P}$

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 impliziert $\mathsf{coNP}$

Glasser, Pavan, Selman und Sengupta, " Properties of NP-complete sets ", SIAM J. Comput. 36 (2), 516–542.

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

Joshua Grochow
quelle

ECCC Draft

Kaveh

Durch starke Hardcore-Funktionen (und Iteration ) implizieren Einweg-Permutationen Pseudozufallsgeneratoren.

@ 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

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

Interessante Frage. Die Aussage

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

ist äquivalent zu:

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

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

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