os idiomas do NP Complete estão fechados em alguma operação regular?

Tentei procurar on-line, mas não consegui encontrar nenhuma declaração definitiva. Faria sentido para mim que Union e Intersection de duas linguagens NPC produzissem uma linguagem não necessariamente na NPC. Também é verdade que os idiomas NPC não estão fechados nas operações complemento, concatenação e estrela kleene?

Para todos os exemplos nesta resposta, estou usando o alfabeto como $\{0,1\}$. Observe que os idiomas$\emptyset$ e $\{0,1\}^*$definitivamente não são NP- completos.

• A classe de idiomas completos NP não é fechada sob interseção. Para qualquer idioma completo do  NP$L$, deixei $L_0 = \{0w\mid w\in L\}$ e $L_1 = \{1w\mid w\in L\}$. $L_0$ e $L_1$ambos são NP- completos, mas$L_0\cap L_1 = \emptyset$.

• A classe de idiomas completos NP não está fechada em união. Dados os idiomas completos do NP$L_0$ e $L_1$ da parte anterior, deixe $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ e $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$. $L'_0$ e $L'_1$ambos são NP- completos, mas$L'_0\cup L'_1 = \{0,1\}^*\!$.

• A classe de idiomas completos NP não está fechada sob concatenação. Considere os idiomas completos do NP$L'_0$ e $L'_1$da parte anterior. Como os dois idiomas contêm $\varepsilon$, temos $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.

• A classe de idiomas completos NP não está fechada sob a estrela Kleene. Para qualquer idioma completo do  NP$L$, $L\cup \{0,1\}$é NP- completo, mas$\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.

• Se a classe de problemas completos de NP for encerrada sob complementação, NP  =  coNP . Se isso é verdade ou não, é um dos principais problemas em aberto na teoria da complexidade.

Dê uma olhada nas provas de união, interseção, concatenação e estrela kleene das línguas NP, aqui . Parece que um argumento semelhante poderia ser feito para linguagens NP-Complete.

Para notação deixe

• $A$seja um oráculo que decida um problema NP-Complete conhecido como o 3-SAT. Veja a definição de turing redutível
• $L_1$ e $L_2$ são idiomas NP-completos
• $M_1$ e $M_2$ são máquinas de Turing que decidem $L_1$ e $L_2$ usando $A$.
• $L_3$ é $L_1 \cup L_2$
• $M_3$ é uma máquina de turing que decide $L_3$

No caso da união de 1 , podemos criar uma nova máquina$M_3$ que decide $L_3$ chamando $M_1$ e $M_2$como sub-rotinas. Por sua vez, cada vez$M_1$ ou $M_2$ é chamado, $A$também é chamado. assim$M_3$ decide $L_3$ usando $A$. Pelo argumento de 1 , o tempo de execução de$M_3$ está em P e já que usa $A$ como sub-rotina, $L_3$é NP-completo. Em outras palavras,$L_3$ é NP-Completo pela mesma razão que $L_1$ e $L_2$ são NP-completos.

O mesmo argumento pode ser feito de interseção e parece que argumentos semelhantes poderiam ser feitos para concatenação e estrela de kleene.

No caso de elogio, parece provável que seja difícil provar pelas mesmas razões que é difícil provar elogio em NP.