8
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ just a note: regular operations are union, concatenation and Kleene star and not intersection and complement $\endgroup$ – A.Schulz Apr 30 '14 at 19:14
  • $\begingroup$ Why not intersection and complement? I haven't seen any formal definition of regular operations anywhere. $\endgroup$ – Tushar Apr 30 '14 at 19:18
  • $\begingroup$ @Tushar Indeed: union, concatenation and Kleene star are regular operations, whereas union, intersection and complement are Boolean operations. See wikipedia. $\endgroup$ – Hendrik Jan May 1 '14 at 0:12
  • $\begingroup$ @Tushar: Because these operations are used to build regular expressions. $\endgroup$ – A.Schulz May 1 '14 at 16:42
15
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Excluding the complement, aren't NP-complete languages closed under all of those? Or is that for P? $\endgroup$ – Adjit Dec 14 '17 at 5:17
  • $\begingroup$ @Adjit Um. I proved that NP is closed under none of them. $\endgroup$ – David Richerby Dec 14 '17 at 6:45
  • $\begingroup$ For your specific language. But I guess I'm not seeing how {0, 1}* is not NP-complete. If you take, for instance, the intersection of 2 NP-complete languages shouldn't you get an NP-complete language, thereby making NP closed under intersection? $\endgroup$ – Adjit Dec 15 '17 at 2:19
  • $\begingroup$ {0, 1}* and the empty language are regular, thus decidable in polynomial time and not NP-Complete. @DavidRicherby showed that there exist two NP-Complete languages the intersection of which is not NP-Complete. That is sufficient to prove NPC is not closed under intersection. $\endgroup$ – weirdev May 5 at 23:18
  • $\begingroup$ @weirdev No! $\emptyset$ and $\Sigma^*$ are not NP-complete because no other languages reduce to them. It's not enough to say that they're in P -- we don't know that languages in P can't be NP-complete. $\endgroup$ – David Richerby May 5 at 23:39
-2
$\begingroup$

Take a look at the proofs for union, intersection, concatenation, and kleene star of NP languages, here. Its seems like a similar argument could be made for NP-Complete languages.

For notation let

  • $A$ be a oracle that decides a known NP-Complete problem like 3-SAT. See the definition of turing reducible
  • $L_1$ and $L_2$ are NP-Complete languages
  • $M_1$ and $M_2$ are Turing machines that decide $L_1$ and $L_2$ using $A$.
  • $L_3$ is $L_1 \cup L_2$
  • $M_3$ is a turing machine that decides $L_3$

In the case of union from 1, we can create a new machine $M_3$ that decides $L_3$ by calling $M_1$ and $M_2$ as sub routines. In turn, each time $M_1$ or $M_2$ is called, $A$ is also called. So $M_3$ decides $L_3$ using $A$. By the argument from 1, the running time of $M_3$ is in P and since it uses $A$ as a subroutine, $L_3$ is NP-Complete. In other words, $L_3$ is NP-Complete for the same reason that $L_1$ and $L_2$ are NP-Complete.

The same argument can be made intersection and it looks like similar arguments could be made for concatenation, and kleene star.

In the case of compliment, it seems likely to be difficult to prove for the same reasons is difficult to prove compliment in NP.

$\endgroup$
  • $\begingroup$ NP-completeness is defined in terms of many-one reductions, not oracle reductions. Further, the NP-complete languages are definitely not closed under union or intersection. If they're closed under complement, then NP=coNP, which is a major open question. $\endgroup$ – David Richerby Apr 30 '14 at 18:54
  • $\begingroup$ In Stephen Cook's 1971 paper[1] which defines NP-Completeness he uses a Query machine which is the same concept as an Oracle. You should also check out the link above on turing reducibility. [1] chell.co.uk/media/product/_master/1/files/… $\endgroup$ – joebloggs Apr 30 '14 at 18:59
  • $\begingroup$ @joebloggs: I can see from your argument that union and intersection of two NP-Complete languages is NP. However, it still doesn't prove whether it is NP-complete. You have to reduce the union or intersection of two NP-complete decision problem to a NP-complete decision problem to show that. $\endgroup$ – Tushar Apr 30 '14 at 19:01
  • $\begingroup$ @DavidRicherby: You say that the NP-complete languages are definitely not closed under union or intersection. I am interested in looking at the proof for that. Do you have any references for that proof? $\endgroup$ – Tushar Apr 30 '14 at 19:04
  • 2
    $\begingroup$ @joebloggs: Your argument works for NP-languages, but NOT for NP-complete languages. To prove that a language L is Np-complete, you need to provide a polynomial reduction from L to a known NP-complete language. As for David's answer, P is closed under intersection, because both empty language and universal language are in P (hence, they are in NP too), but they are not NP-complete. Hope that makes it clear! $\endgroup$ – Tushar Apr 30 '14 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.