I think I have a hard time understanding the definition for NP. It says: "All decision problem where every yes-instance can be verified in polynomial time". But doesn't this just mean that every possible solution can be verified to be yes or no in polynomial time? If co-NP then is verifying no-instances isn't NP already doing that?

So simply put, if you can verifiy yes-instances can't you implicitly verifiy no-instances?


The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it. The formal definitions are given at our reference question on NP.

A decision problem is in NP if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that:

  • For every "yes" instance $x$, there is some $y$ with $|y|\leq p(|x|)$ such that $M$ accepts the string $x,y$;

  • For every "no" instance $x$, $M$ rejects all strings $x,y$.

So, for example, 3-COLOURABILITY is in NP: the string $y$ is just a description of a $3$-colouring and $M$ accepts $x,y$ if $y$ is a valid $3$-colouring of the graph $x$ and rejects otherwise. The point is not that you can "verify 'yes' instances" but, rather, that every "yes" instance has a certificate $y$ that you can use to easily prove that it really is a "yes" instance.

But there's a significant asymmetry in the definition. If you give $M$ a "yes" input and a certificate $y$, then $M$ will say "I agree – that's a 'yes' instance." However, there's no input you can give it that will cause it to say "I agree – that's a 'no' instance." For any certificate you try, it will just say "That doesn't convince me it's a 'yes'." You could, of course, try all possible certificates. That would certainly prove that you had a "no" instance but there's a problem: there are exponentially many possible certificates to try, so trying all of them doesn't give you a polynomial-time algorithm.

| cite | improve this answer | |

No. As an intuitive argument, consider verifying primality. It is easy to show you that $8633$ is composite by $8633 = 89 \times 97$, whereas it is not evident that how this helps to develop a method to persuade you that some number is indeed a prime.

| cite | improve this answer | |
  • $\begingroup$ Bad example: primality is in P and, even before that was known, it was known to be in co-NP. $\endgroup$ – David Richerby Dec 12 '17 at 15:34
  • $\begingroup$ @DavidRicherby Surely I know that. $\endgroup$ – Lwins Dec 12 '17 at 15:35
  • $\begingroup$ @Ferus I am sorry that I could not get your point. Would you please explain more specifically? $\endgroup$ – Lwins Dec 12 '17 at 15:45
  • $\begingroup$ @Lwins Never mind, realized the co-NP would have different looking solutions. $\endgroup$ – Ferus Dec 12 '17 at 15:50

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.