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 = {0wmid win L}$ and $L_1 = {1wmid win L}$. $L_0$ and $L_1$ are both NP-complete but $L_0cap 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 {1wmid win {0,1}^*}cup{varepsilon}$ and $L’_1 = L_1cup {0wmid win {0,1}^*}cup{varepsilon}$. $L’_0$ and $L’_1$ are both NP-complete but $L’_0cup 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’_0cup L’_1 = {0,1}^*!$.
- The class of NP-complete languages is not closed under Kleene star. For any NP-complete language $L$, $Lcup {0,1}$ is NP-complete but $big(Lcup {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
