# Are all subsets of NP-complete languages also NP-complete?

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.

## 1 Answer

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.

• Fimus is 2SAT (in P) a subset of SAT (NP-Complete)? if yes I can use as example! – Gianni Spear Nov 28 '19 at 22:17
• A language $L_1$ is a subset of a language $L_2$ if every $x \in L_1$ satisfies $x \in L_2$. – Yuval Filmus Nov 28 '19 at 22:21
• this means the 2SAT is not a subset of SAT – Gianni Spear Nov 28 '19 at 22:28
• SAT consists of all satisfiable CNFs. 2SAT consists of all satisfiable 2CNFs. A satisfiable 2CNF is also a satisfiable CNF. – Yuval Filmus Nov 28 '19 at 22:46
• 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 – Gianni Spear Nov 28 '19 at 23:25