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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.