A problem is in NP if a correct answer to it can be verified to be so in polynomial time.

A problem is in co-NP if an incorrect answer to it can be verified to be so in polynomial time.

P is a subset of the intersection of the sets NP and co-NP.

My question is: what is a specific problem that is in the intersection of co-NP & NP, but is not in P?

  • $\begingroup$ mathoverflow.net/questions/34889/… $\endgroup$ – sdcvvc Dec 31 '13 at 10:22
  • 4
    $\begingroup$ Your definition of co-NP is incorrect. For example, you can easily verify that a proposed satisfying assignment to a Boolean formula actually makes the formula false but that doesn't mean that SAT is in co-NP. $\endgroup$ – David Richerby Dec 31 '13 at 11:46
  • 5
    $\begingroup$ Dude, there is no need to shout. You do not need stars and all-capitals in your title. $\endgroup$ – David Richerby Dec 31 '13 at 17:36
  • 4
    $\begingroup$ Stop rolling back people's edits when they fix your post. There's no markup in titles. $\endgroup$ – Gilles 'SO- stop being evil' Dec 31 '13 at 20:26
  • 1
    $\begingroup$ @ashley Your question is not the place to complain about how you feel you are being mistreated. If you feel that your question is being treated unfairly, take the issue up on meta. (Participation on meta requires reputation at least 5, which you have.) $\endgroup$ – David Richerby Jan 11 '14 at 2:07

An answer to your question would be a problem $p$ which is in $\mathop{NP}\cap\mathop{coNP}$, and thus in $\mathop{NP}$, but not in $P$. Existence of such a problem would easily imply $P\neq\mathop{NP}$, which is a seriously open problem to this date. That is to say, no one can answer your question yet.

  • $\begingroup$ The question is, can we exhibit an explicit problem $L$ in NP$\cap$coNP such that $L \in P$ implies P=NP. For example, SAT is in NP, and if SAT$\in$P then P=NP. $\endgroup$ – Yuval Filmus Dec 31 '13 at 12:54
  • 1
    $\begingroup$ That's an interesting question, and sdcvvc's link gives an answer to that. $\endgroup$ – Untitled Dec 31 '13 at 13:52
  • $\begingroup$ @Untitled That's a quick answer. A worthy way of looking into the intractability of the problems is from the angle of "what we know so far." Check out the NPI "zone" i noted in my Q for a broader angle for you. $\endgroup$ – ashley Dec 31 '13 at 17:38
  • $\begingroup$ @ashley I can't find it. Do you have a link? $\endgroup$ – Untitled Dec 31 '13 at 18:23
  • $\begingroup$ @Untitled - en.wikipedia.org/wiki/NP-intermediate. $\endgroup$ – ashley Dec 31 '13 at 20:11

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.