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.
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}$.
