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



Your Answer

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