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 maweki on Wednesday August 16, 2017 @06:24PM (#15031876)

I could be convinced that P=NP, but that would also mean that Co-NP=P and I just couldn't wrap my mind around that one.

Co-NP just seems so much harder than NP.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by likelynew on Wednesday August 16, 2017 @10:16PM (#15033237)

I believe it's opposite i.e. if P=Co-NP, then P=NP.

[ Parent | on HN ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by maweki on Thursday August 17, 2017 @07:11AM (#15035624)

This is all contained in the collapse of the hierarchy, no matter which way you look at it. It will all be the same.

[ Parent | on HN ]

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 ]

Re:On Norbert Blum’s claimed proof that P does not equal NP by yorwba on Thursday August 17, 2017 @12:48AM (#15033879)

Because P=Co-P, that's the same thing.

[ Parent | on HN ]