# Is there a specific problem that is in both NP and co-NP but not in P?

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?

• mathoverflow.net/questions/34889/… – sdcvvc Dec 31 '13 at 10:22
• 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. – David Richerby Dec 31 '13 at 11:46
• Dude, there is no need to shout. You do not need stars and all-capitals in your title. – David Richerby Dec 31 '13 at 17:36
• Stop rolling back people's edits when they fix your post. There's no markup in titles. – Gilles 'SO- stop being evil' Dec 31 '13 at 20:26
• @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.) – 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.
• 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. – Yuval Filmus Dec 31 '13 at 12:54