On Norbert Blum’s claimed proof that P does not equal NP

Re:On Norbert Blum’s claimed proof that P does not equal NP by likelynew on Friday August 18, 2017 @04:54AM (#15044592)

So, P=NP implies P=Co-NP?

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by maweki on Sunday August 20, 2017 @02:27AM (#15057204)

Yes. Since we already know that P=Co-P, if P were to be shown equal to NP then P=NP=Co-NP=Co-P.

All these classes would turn out to be the same since P is closed under complement. Then NP would be as well and everything is equal.

That's why this result sometimes is called the collapse if the complexity hierarchy.

[ Parent | on HN ]