Talk:PH (complexity)

Proof of P=NP if and only if P=PH

Let P=NP. P is closed under complement, therefore NP=co-NP. NP = Σ1, and co-NP = ∏1. Therefore Σ1 = ∏1. If Σi = ∏i for any i the entire hierarchy collapses to Σi., So PH = Σ1 = NP = P.

Let P=PH. NP=Σ1⊆PH=P, Therefore NP⊆P and trivially P⊆NP. Therefore, P=NP

Note this proof cites Wikipedia and should not be added verbatim to the page Yonatan Vernik (talk) 19:15, 30 November 2018 (UTC)

References

forrelation

The article says there is “some evidence” that BQP is not contained in PH. Actually, there’s a proof. Forrelation is in BQP, but not in PH. https://epubs.siam.org/doi/abs/10.1137/15M1050902