2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ That doesn't follow. $\Sigma^*$ is in Co-NP, but there are undecidable languages. $\endgroup$ – G. Bach Dec 11 '13 at 16:03
  • $\begingroup$ could you elaborate a little more, sorry i kind of understand but not entirely $\endgroup$ – Jen Stone Dec 11 '13 at 16:11
  • 1
    $\begingroup$ 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... $\endgroup$ – Jen Stone Dec 11 '13 at 16:15
  • $\begingroup$ ... such as any undecidable language at all! $\endgroup$ – David Richerby Dec 11 '13 at 16:33
  • 1
    $\begingroup$ @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. $\endgroup$ – G. Bach Dec 11 '13 at 21:40
3
$\begingroup$

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

$\endgroup$

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.