# 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/… Commented Dec 31, 2013 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. Commented Dec 31, 2013 at 11:46
• Dude, there is no need to shout. You do not need stars and all-capitals in your title. Commented Dec 31, 2013 at 17:36
• Stop rolling back people's edits when they fix your post. There's no markup in titles. Commented Dec 31, 2013 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.) Commented Jan 11, 2014 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. Commented Dec 31, 2013 at 12:54