23 ms·
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
by maweki 9y ago
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.
- likelynew 9y agoI believe it's opposite i.e. if P=Co-NP, then P=NP.
- yorwba 9y agoBecause P=Co-P, that's the same thing.
- deleted 9y ago[deleted]
- maweki 9y agoThis is all contained in the collapse of the hierarchy, no matter which way you look at it. It will all be the same.
- likelynew 9y agoSo, P=NP implies P=Co-NP?
- maweki 9y agoYes. 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.