# 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.

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.
• 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