3
$\begingroup$

I often read in Complexity literature that NP∩coNP is unlikely to have any complete problems. Is that unlikelihood "proved" ?

By proved, I mean that there would be a theorem that would relate the existence of such a problem to, by instance, the collapse of PH, or any other equality that is strongly believed not to hold (and that at least would be a major breakthrough).

Improve this question
$\endgroup$
1

0

Reset to default

Your Answer

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