The statement about P=NP

120 Views Asked by At

On this https://en.wikipedia.org/wiki/PH_(complexity) page there is a statement that: "P = NP if and only if P = PH. This may simplify a potential proof of P ≠ NP, since it is only necessary to separate P from the more general class PH" Is it true?

1

There are 1 best solutions below

0
On BEST ANSWER

Yes, it's true and it's covered in most complexity theory textbooks. I just checked Arora and Barak, Kozen, and Moore and Mertens, which are the ones I have at hand here at home. An optimist would say that the proof of $P\neq NP$ is potentially easier. Others see the glass half-empty: given that P=NP would lead to a collapse of the entire polynomial hierarchy, it's even less likely that P=NP. Of course, they don't disagree.