2
$\begingroup$

What are the problems that are in co-NP but not in NP?

i.e, those problems where incorrect strings can be deterministically verified in polynomial time but the correct strings can't be.

$\endgroup$
  • $\begingroup$ Do you know the definition of coNP? Are you familiar with NP-complete problems? Can you use this to find a good candidate for such a problem? Note that we don't actually know whether coNP=NP or not. It is conjectured that $coNP\neq NP$, and it is widely believed to be the case. $\endgroup$ – Shaull Mar 6 '17 at 7:52
3
$\begingroup$

co-NP is the set of complements of problems that are in NP. So co-NP contains problems such as non-3-colourability, Boolean unsatisfiability and so on. Most complexity theorists believe that NP$\,\neq\,$co-NP and one consequence of this is that the complement of any NP-complete problem would be in co-NP but not in NP.

Wikipedia has more information on co-NP.

$\endgroup$
3
$\begingroup$

Your question assumes $NP \neq coNP$, which is currently unknown (but generally assumed to be true). If $NP = coNP$, there is no problem satisfying your requirements.

If $NP \neq coNP$, the complement of any NP-complete problem works. You can find a list on Wikipedia.

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