3 ms·
I believe it's opposite i.e. if P=Co-NP, then P=NP.
by likelynew 9y ago
I 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.