Sind NP Complete-Sprachen im regulären Betrieb geschlossen?

Ich habe versucht, online zu suchen, konnte aber keine endgültigen Aussagen finden. Es würde für mich Sinn machen, dass die Vereinigung und Kreuzung zweier NPC-Sprachen eine Sprache hervorbringen würde, die nicht unbedingt im NPC enthalten ist. Stimmt es auch, dass NPC-Sprachen nicht unter den Operationen Komplement, Verkettung und Kleene-Sterne geschlossen werden?

Für alle Beispiele in dieser Antwort nehme ich das Alphabet als . Beachten Sie, dass die Sprachen ∅ und { 0 , 1 } ∗ definitiv nicht NP- vollständig sind.$\{0,1\}$$\emptyset$$\{0,1\}^*$

• Die Klasse der NP- vollständigen Sprachen wird unter Schnittmenge nicht geschlossen. Für jede NP- vollständige Sprache  sei L 0 = { 0 w ∣ w ∈ L } und L 1 = { 1 w ∣ w ∈ L } . L 0 und  L 1 sind beide NP- vollständig, aber L 0 ∩ L 1 = ∅ .$L$$L_0 = \{0w\mid w\in L\}$$L_1 = \{1w\mid w\in L\}$$L_0$$L_1$$L_0\cap L_1 = \emptyset$

• Die Klasse der NP- vollständigen Sprachen ist unter Union nicht geschlossen. Bei den NP- vollständigen Sprachen und  L 1 aus dem vorherigen Teil sei L ' 0 = L 0 ∪ { 1 w ∣ w ∈ { 0 , 1 } ∗ } ∪ { ε } und L ′ 1 = L 1 ∪ { 0 w ∣ w ∈ { 0 $L_0$$L_1$$L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ . L ' 0 und  L ' 1 sind beideNP-vollständig, aber L ' 0 ∪ L ' 1 = { 0 , 1 } $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$$L'_0$$L'_1$$L'_0\cup L'_1 = \{0,1\}^*\!$.

• Die Klasse der NP- vollständigen Sprachen wird bei Verkettung nicht geschlossen. Betrachten Sie die NP- vollständigen Sprachen und  L ' 1 aus dem vorherigen Teil. Da beide Sprachen ε enthalten  , haben wir L ' 0 L ' 1 ⊇ L ' 0 ∪ L ' 1 = { 0 , 1 } $L'_0$$L'_1$$\varepsilon$$L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.

• Die Klasse der NP- vollständigen Sprachen ist unter Kleene-Stern nicht geschlossen. Für jede NP -komplette Sprache  , L ∪ { 0 , 1 } ist NP -komplette aber ( L ∪ { 0 , 1 } ) * = { 0 , 1 } $L$$L\cup \{0,1\}$$\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.

• Wenn die Klasse der NP- vollständigen Probleme unter Komplementation geschlossen wird, ist NP  =  coNP . Ob dies wahr ist oder nicht, ist eines der wichtigsten offenen Probleme in der Komplexitätstheorie.

Schauen Sie sich hier die Beweise für Vereinigung, Schnittmenge, Verkettung und Kleene-Stern der NP-Sprachen an . Es scheint, als könnte ein ähnliches Argument für NP-vollständige Sprachen vorgebracht werden.

Zur Notation lassen

• Orakel, das über ein bekanntes NP-Complete-Problem wie 3-SAT entscheidet. Siehe die Definition von$A$ Turing reduzierbar
• und L $L_1$$L_2$ sind NP-vollständige Sprachen
• und M 2 sind Turingmaschinen, die L 1 und L 2 mit$M_1$$M_2$$L_1$$L_2$$A$ .
• ist L 1 ∪ L $L_3$$L_1 \cup L_2$
• ist eine Turingmaschine, die über L 3 entscheidet$M_3$$L_3$

Im Fall der Vereinigung von 1 können wir eine neue Maschine erstellen , die L 3 entscheidet, indem wir M 1 und M 2 als Unterroutinen aufrufen . Jedes Mal, wenn M 1 oder M 2 aufgerufen wird, wird wiederum auch A aufgerufen. So M 3 entscheidet L 3 mit A . Nach dem Argument von 1 ist die Laufzeit von M 3 in P und da A als Unterprogramm verwendet wird, ist L 3 NP-vollständig. Mit anderen Worten,$M_3$$L_3$$M_1$$M_2$$M_1$$M_2$$A$$M_3$$L_3$$A$$M_3$$A$$L_3$ ist NP-vollständig aus dem gleichen Grund, aus dem L 1 und L 2 NP-vollständig sind.$L_3$$L_1$$L_2$

Das gleiche Argument kann als Schnittpunkt verwendet werden, und es sieht so aus, als könnten ähnliche Argumente für die Verkettung und den Kleene-Stern vorgebracht werden.

Im Falle eines Komplimentes scheint es wahrscheinlich schwierig zu sein, aus den gleichen Gründen zu beweisen, dass es schwierig ist , ein Kompliment in NP zu beweisen.