0
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ mathoverflow.net/questions/34889/… $\endgroup$
    – sdcvvc
    Dec 31, 2013 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$ Dec 31, 2013 at 11:46
  • 5
    $\begingroup$ Dude, there is no need to shout. You do not need stars and all-capitals in your title. $\endgroup$ Dec 31, 2013 at 17:36
  • 4
    $\begingroup$ Stop rolling back people's edits when they fix your post. There's no markup in titles. $\endgroup$ Dec 31, 2013 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$ Jan 11, 2014 at 2:07

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
7
  • $\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$ Dec 31, 2013 at 12:54
  • 1
    $\begingroup$ That's an interesting question, and sdcvvc's link gives an answer to that. $\endgroup$
    – Untitled
    Dec 31, 2013 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, 2013 at 17:38
  • $\begingroup$ @ashley I can't find it. Do you have a link? $\endgroup$
    – Untitled
    Dec 31, 2013 at 18:23
  • $\begingroup$ @Untitled - en.wikipedia.org/wiki/NP-intermediate. $\endgroup$
    – ashley
    Dec 31, 2013 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.