les langues NP Complete sont-elles fermées dans le cadre d'opérations régulières?

J'ai essayé de chercher en ligne, mais je n'ai trouvé aucune déclaration définitive. Il serait logique pour moi que l'union et l'intersection de deux langues NPC produisent une langue qui n'est pas nécessairement dans NPC. Est-il également vrai que les langages des PNJ ne sont pas fermés sous le complément, la concaténation et les opérations des étoiles kleene?

Pour tous les exemples de cette réponse, je considère que l'alphabet est . Notez que les langues et sont certainement pas complètes en NP .$\{0,1\}$$\emptyset$$\{0,1\}^*$

• La classe des langages complets NP n'est pas fermée sous intersection. Pour toute NP langue -complete  , laissez et . et  sont tous deux NP- mais .$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$

• La classe des langues complètes NP n'est pas fermée sous union. Étant donné les langages NP et  de la partie précédente, laissez et . et  sont tous deux NP- complétés mais.$L_0$$L_1$$L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$$L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$$L'_0$$L'_1$$L'_0\cup L'_1 = \{0,1\}^*\!$

• La classe des langages complets NP n'est pas fermée sous concaténation. Considérez les langages NP- complets et  de la partie précédente. Puisque les deux langues contiennent  , nous avons.$L'_0$$L'_1$$\varepsilon$$L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$

• La classe des langues complètes NP n'est pas fermée sous l'étoile de Kleene. Pour tout langage complet  NP , est NP complet mais.$L$$L\cup \{0,1\}$$\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$

• Si la classe des problèmes NP complets est fermée par complémentation, alors NP  =  coNP . Que cela soit vrai ou non est l'un des principaux problèmes ouverts de la théorie de la complexité.

Jetez un œil aux preuves d'union, d'intersection, de concaténation et d'étoile kleene des langages NP, ici . Il semble qu'un argument similaire pourrait être avancé pour les langues NP-Complete.

Pour la notation,

• $A$ être un oracle qui décide un problème NP-complet connu comme 3-SAT. Voir la définition de turing réductible
• $L_1$ et sont des langues NP-Complete$L_2$
• $M_1$ et sont les machines qui décident de Turing et en utilisant .$M_2$$L_1$$L_2$$A$
• $L_3$ est$L_1 \cup L_2$
• $M_3$ est une machine de turing qui décide$L_3$

Dans le cas de l'union à partir de 1 , on peut créer une nouvelle machine qui décide en appelant$M_3$$L_3$$M_1$ et $M_2$comme sous-routines. À son tour, à chaque fois$M_1$ ou $M_2$ est appelé, $A$est également appelé. Donc$M_3$ décide $L_3$ en utilisant $A$. Par l'argument de 1 , le temps d'exécution de$M_3$ est en P et puisqu'il utilise $A$ comme sous-programme, $L_3$est NP-Complete. En d'autres termes,$L_3$ est NP-Complete pour la même raison que $L_1$et sont NP-Complete.$L_2$

Le même argument peut être fait intersection et il semble que des arguments similaires pourraient être avancés pour la concaténation et l'étoile kleene.

Dans le cas du compliment, il semble probable qu'il soit difficile de prouver pour les mêmes raisons qu'il est difficile de prouver le compliment en NP.