patternModerate
Are NP-Complete languages closed under any regular operations?
Viewed 0 times
operationsarelanguagesanyregularclosedcompleteunder
Problem
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?
Solution
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.
-
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.
Context
StackExchange Computer Science Q#24264, answer score: 19
Revisions (0)
No revisions yet.