4 ms·
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 clos
by maweki 9y ago
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.