patternMinor
Relationship between PP and PH
Viewed 0 times
andbetweenrelationship
Problem
Toda's theorem says that $PH \subset P^{PP}$. Does this imply any relationship between $PH$ and $PP$ that does not involve oracles? Does it imply either that $PH \subset PP$ or that $PP \subset PH$? Is it known or conjectured whether either of those hold?
Solution
No, it's not known whether $PH \subset PP$, and it's not known whether $PP \subset PH$. Neither of those is implied by Toda'a theorem.
This blog article cites a paper by Beigel giving some weak evidence to suspect that $PH \not\subset PP$ (that $PH$ is not contained in $PP$). Please be warned that this is very weak evidence and doesn't really prove anything. The result says that there's a relativized world where $P^{NP}$ is not contained in $PP$. It follows that there's a relativized world where $PH$ is not contained in $PP$. This might suggest the conjecture that $PH \not\subset PP$. Or, at least, it suggests that proving $PH \subset PP$ might require special proof techniques (non-relativizing proof techniques; and most, but not all, known proof techniques do relativize).
This blog article cites a paper by Beigel giving some weak evidence to suspect that $PH \not\subset PP$ (that $PH$ is not contained in $PP$). Please be warned that this is very weak evidence and doesn't really prove anything. The result says that there's a relativized world where $P^{NP}$ is not contained in $PP$. It follows that there's a relativized world where $PH$ is not contained in $PP$. This might suggest the conjecture that $PH \not\subset PP$. Or, at least, it suggests that proving $PH \subset PP$ might require special proof techniques (non-relativizing proof techniques; and most, but not all, known proof techniques do relativize).
Context
StackExchange Computer Science Q#62787, answer score: 3
Revisions (0)
No revisions yet.