are NP Complete languages closed under any regular operations?

Answered By : David Richerby

For all of the examples in this answer, I'm taking the alphabet to be $\{0,1\}$. Note that the languages $\emptyset$ and $\{0,1\}^*$ are definitely not NP-complete.

• The class of NP-complete languages is not closed under intersection. For any NP-complete language $L$, let $L_0 = \{0w\mid w\in L\}$ and $L_1 = \{1w\mid w\in L\}$. $L_0$ and $L_1$ are both NP-complete but $L_0\cap L_1 = \emptyset$.

• The class of NP-complete languages is not closed under union. Given the NP-complete languages $L_0$ and $L_1$ from the previous part, let $L'_0 = L_0 \cup \{1w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$ and $L'_1 = L_1\cup \{0w\mid w\in \{0,1\}^*\}\cup\{\varepsilon\}$. $L'_0$ and $L'_1$ are both NP-complete but $L'_0\cup L'_1 = \{0,1\}^*\!$.

• The class of NP-complete languages is not closed under concatenation. Consider the NP-complete languages $L'_0$ and $L'_1$ from the previous part. Since both languages contain $\varepsilon$, we have $L'_0L'_1 \supseteq L'_0\cup L'_1 = \{0,1\}^*\!$.

• The class of NP-complete languages is not closed under Kleene star. For any NP-complete language $L$, $L\cup \{0,1\}$ is NP-complete but $\big(L\cup \{0,1\}\big)^* = \{0,1\}^*\!$.

• If the class of NP-complete problems is closed under complementation, then NP = coNP. Whether this is true or not is one of the major open problems in complexity theory.

Problem Detail: 

I have tried looking online, but I couldn't find any definitive statements. It would make sense to me that Union and Intersection of two NPC languages would produce a language not necessarily in NPC. Is it also true that NPC languages are not closed under the complement, concatenation, and kleene star operations?

Asked By : user16742

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/24264