# Is Co-NP closed under taking subset?

I have a question on my homework causing some confusion.

If L is a strict subset of L', and L' is a member of Co-NP, is L a member of Co-NP? True of False

Now I understand what belonging to Co-NP. Essentially means instead of deciding a yes instance we're deciding a no instance of the decidable problem. I'm stuck on interpreting L' and what it is.

My guess at this point is that L is a member of Co-NP since it's a subset of L' which we're given is in Co-NP.

• That doesn't follow. $\Sigma^*$ is in Co-NP, but there are undecidable languages. – G. Bach Dec 11 '13 at 16:03
• could you elaborate a little more, sorry i kind of understand but not entirely – Jen Stone Dec 11 '13 at 16:11
• so is what you're saying is Σ* is in Co-NP because we can verify in polynomial time whether a string is not in the language. However within this language, there are undecidable languages that are not members of co-NP such as... – Jen Stone Dec 11 '13 at 16:15
• ... such as any undecidable language at all! – David Richerby Dec 11 '13 at 16:33
• @JenStone Yes, that's exactly it. That proof even shows that any complexity class that contains $\Sigma^*$ but doesn't contain all undecidable languages is not closed under taking subsets. That's pretty much all interesting complexity classes out there. – G. Bach Dec 11 '13 at 21:40

For a language $L' \in \mathsf{coNP}$, there are certificates for all NO instances, which is to say inputs $x \notin L'$, which could be efficiently verified and used as proof that $x \notin L$. Suppose that $L \subset L'$: the fact that there are certificates for all NO instances $x \notin L'$ isn't enough to allow us to determine decisively if $x \notin L$, because we could have an input $x \in L' \smallsetminus L$.
Thus, the certificates for $L'$ are not sufficient to provide certificates for $L$, and we cannot conclude that $L \in \mathsf{coNP}$. Indeed, as @G.Bach indicates in the comments, there are examples where $L' \in \mathsf{coNP}$ and $L$ is not even a decideable language. Modifying his example, consider $$L' = \Bigl\{ x \in \{0,1\}^\ast \;\Big|\; |x| \text{ is prime} \Bigr\}$$ which has certificates for NO instances simply by giving a non-trivial factor for $|x|$ on any input $x \notin L'$. Then $L' \in \mathsf{coNP}$, and indeed $L' \in \mathsf P$: not only because the AKS algorithm puts primality testing in $\mathsf P$, but because (the input being expressed in unary) even trial division would represent an efficient algorithm. However, the language $$L = \left\{ x \in L' \;\left| \begin{array}{c} x \text{ encodes a Turing machine} \\ \text{and an input on which it halts,} \\ \text{padded with 0s} \end{array} \right\}\right.$$ using whichever encoding of Turing machines that you like will not even be a decideable language in general, and so it will definitely not be in $\mathsf{coNP}$.