Talk:PH (complexity)
Add topicLatest comment: 7 years ago by Yonatan Vernik in topic Proof of P=NP if and only if P=PH
 | This redirect does not require a rating on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||
Proof of P=NP if and only if P=PH
[edit]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.[1], 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)
forrelation
[edit]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