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

205 Views Asked by At

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?

1

There are 1 best solutions below

2
On BEST ANSWER

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}$.