1
$\begingroup$

Is the following assertion true or false?

If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete.

I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-coloring is an infinite subset of this which is in P (see link). Therefore, for me, the assertion is false. However, I'm working through languages, and I cannot figure out an example (with language) useful to show false the assertion.

$\endgroup$
1
$\begingroup$

Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete.

You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ colors, and let $Q$ consist of all pairs $(G,2)$ such that $G$ is bipartite; note that $Q \subseteq L$. It is known that $L$ is NP-complete, whereas $Q$ is in P. Therefore $Q$ is not NP-complete unless P=NP.

$\endgroup$
  • $\begingroup$ Fimus is 2SAT (in P) a subset of SAT (NP-Complete)? if yes I can use as example! $\endgroup$ – Gianni Spear Nov 28 '19 at 22:17
  • $\begingroup$ A language $L_1$ is a subset of a language $L_2$ if every $x \in L_1$ satisfies $x \in L_2$. $\endgroup$ – Yuval Filmus Nov 28 '19 at 22:21
  • $\begingroup$ this means the 2SAT is not a subset of SAT $\endgroup$ – Gianni Spear Nov 28 '19 at 22:28
  • $\begingroup$ SAT consists of all satisfiable CNFs. 2SAT consists of all satisfiable 2CNFs. A satisfiable 2CNF is also a satisfiable CNF. $\endgroup$ – Yuval Filmus Nov 28 '19 at 22:46
  • $\begingroup$ Sorry now, I'm a little bit confused. If you write "A satisfiable 2CNF is also a satisfiable CNF" for me means 2SAT (P) is a subset of SAT (NP-complete)? from your sentence I understand (if I do not wrong) 2SAT is a subset of SAT $\endgroup$ – Gianni Spear Nov 28 '19 at 23:25

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.