¿Se cierran los idiomas NP Complete en alguna operación regular?

He intentado buscar en línea, pero no pude encontrar ninguna declaración definitiva. Para mí tendría sentido que Unión e Intersección de dos idiomas de la APN producirían una lengua no necesariamente en la APN. ¿También es cierto que los lenguajes NPC no están cerrados bajo el complemento, la concatenación y las operaciones de kleene star?

Para todos los ejemplos en esta respuesta, estoy tomando el alfabeto como $\{0,1\}$. Tenga en cuenta que los idiomas$\emptyset$ y $\{0,1\}^*$definitivamente no son NP- completos.

• La clase de idiomas completos de NP no está cerrada bajo intersección. Para cualquier lenguaje NP completo $L$, dejar $L_0 = \{0w\mid w\in L\}$ y $L_1 = \{1w\mid w\in L\}$. $L_0$ y $L_1$son ambos NP- completos pero$L_0\cap L_1 = \emptyset$.

• La clase de lenguajes NP completos no está cerrada bajo unión. Dados los idiomas completos de NP$L_0$ y $L_1$ de la parte anterior, dejemos $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ y $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$. $L'_0$ y $L'_1$son ambos NP- completos pero$L'_0\cup L'_1 = \{0,1\}^*\!$.

• La clase de lenguajes NP completos no está cerrada bajo concatenación. Considere los idiomas completos de NP$L'_0$ y $L'_1$de la parte anterior Dado que ambos idiomas contienen $\varepsilon$, tenemos $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.

• La clase de idiomas NP- completos no está cerrada bajo la estrella de Kleene. Para cualquier lenguaje NP completo $L$, $L\cup \{0,1\}$es NP -completo pero$\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.

• Si la clase de problemas completos de NP se cierra bajo complementación, entonces NP  =  coNP . Si esto es cierto o no es uno de los principales problemas abiertos en la teoría de la complejidad.

Eche un vistazo a las pruebas de unión, intersección, concatenación y estrella de kleene de los idiomas NP, aquí . Parece que se podría hacer un argumento similar para los lenguajes NP-Complete.

Para notación deja

• $A$ser un oráculo que decida un problema NP-Complete conocido como 3-SAT. Ver la definición de turing reducible
• $L_1$ y $L_2$ son idiomas NP-completos
• $M_1$ y $M_2$ son máquinas de Turing que deciden $L_1$ y $L_2$ utilizando $A$.
• $L_3$ es $L_1 \cup L_2$
• $M_3$ es una máquina de Turing que decide $L_3$

En el caso de unión desde 1 , podemos crear una nueva máquina$M_3$ eso decide $L_3$ llamando $M_1$ y $M_2$como sub rutinas. A su vez, cada vez$M_1$ o $M_2$ se llama, $A$es tambien llamado. Entonces$M_3$ decide $L_3$ utilizando $A$. Por el argumento de 1 , el tiempo de ejecución de$M_3$ está en P y ya que usa $A$ como una subrutina $L_3$es NP-Complete. En otras palabras,$L_3$ es NP-Complete por la misma razón que $L_1$ y $L_2$ son NP-Complete.

El mismo argumento se puede hacer intersección y parece que se podrían hacer argumentos similares para la concatenación y la estrella de Kleene.

En el caso del cumplido, parece probable que sea difícil de probar por las mismas razones que es difícil demostrar el cumplido en NP.