If $P = NP \cap coNP$, can $P \ne NP$?

Question

In Scott Aaronson's Quantum Computing since Democritus he writes on page 65:

Indeed, for all we know, it could be the case that $P = NP \cap coNP$ but still $P \ne NP$.

The same statement is in the lecture notes here:

http://www.scottaaronson.com/democritus/lec6.html

I was surprised to read that, until I realized he's talking about $NP$ but not necessarily $NP$-complete problems. So if I understand correctly, if $P = NP \cap coNP$ and $NP \cap coNP$ contains any NP-complete problems, then it is not possible that $P \ne NP$. Is that right?

Yes, your last statement is correct. – Qudit Apr 21 '15 at 03:48 — Qudit, Apr 21 '15 at 03:48
Alright, I posted a more detailed version as an answer :) – Qudit Apr 21 '15 at 04:09 — Qudit, Apr 21 '15 at 04:09

Qudit · Accepted Answer · 2015-04-21T04:23:30.107

1

Your last statement is correct.

If $\mathrm{NP} \cap \mathrm{coNP}$ contains a $\mathrm{NP}$-complete problem, then so does $\mathrm{P}$, which implies that $\mathrm{P} = \mathrm{NP}$.

Currently, it's suspected that $\mathrm{NP} \cap \mathrm{coNP}$ is properly contained in $\mathrm{NP}$, which implies that it does not contain any $\mathrm{NP}$-complete problems. However, this has not been proved. If it were, in particular it would imply that $\mathrm{P} \not= \mathrm{NP}$.

edited Apr 21 '15 at 04:23

answered Apr 21 '15 at 04:04

Qudit

3,221

1

Whew, I'm glad you made that edit! :-) – Paul A Jungwirth Apr 21 '15 at 04:24
Yeah, that was a pretty bad typo... – Qudit Apr 21 '15 at 04:36

If $P = NP \cap coNP$, can $P \ne NP$?

1 Answers1