10
$\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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ just a note: regular operations are union, concatenation and Kleene star and not intersection and complement $\endgroup$
    – A.Schulz
    Apr 30, 2014 at 19:14
  • $\begingroup$ Why not intersection and complement? I haven't seen any formal definition of regular operations anywhere. $\endgroup$
    – Tushar
    Apr 30, 2014 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, 2014 at 0:12
  • $\begingroup$ @Tushar: Because these operations are used to build regular expressions. $\endgroup$
    – A.Schulz
    May 1, 2014 at 16:42

2 Answers 2

Reset to default
19
$\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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Excluding the complement, aren't NP-complete languages closed under all of those? Or is that for P? $\endgroup$
    – Adjit
    Dec 14, 2017 at 5:17
  • $\begingroup$ @Adjit Um. I proved that NP is closed under none of them. $\endgroup$
    – David Richerby
    Dec 14, 2017 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, 2017 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, 2019 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, 2019 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.

Improve this answer
$\endgroup$
11
  • $\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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 at 19:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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