2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The result is only ​ $PH\subseteq P^{PP}$ . ​ ​ ​ If that was known to be strict, then we'd know ​ PP $\not\subseteq$ PH . ​ ​ ​ You might be interested in the other part of Toda's theorem, which is that ​ PH $\subseteq$ BP$\oplus$P . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$ – user12859 Aug 22 '16 at 7:35
  • $\begingroup$ @RickyDemer So you are saying that none of these possibilities has been ruled out: (a) $PH = PP$, (b) $PH \subset PP$, (c) $PP \subset PH$, or (d) $PH$ and $PP$ are incomparable? Is one of these four possibilities generally believed to be the case? $\endgroup$ – tparker Aug 22 '16 at 8:33
  • 1
    $\begingroup$ Yes; PP is not even known to differ from rational-uniform NC$^1$. ​ No, although (a) would imply that PH collapses, since PP has a complete problem. ​ ​ ​ ​ $\endgroup$ – user12859 Aug 22 '16 at 8:55
  • $\begingroup$ @D.W. Sorry, I think I'm misusing the word "relativization." I just mean that does $PH \subset P^{PP}$ imply any inclusion relationship between $PH$ and $PP$ themselves, not between any complexity class relative to any kind of oracle. In other words, does it imply any relation that can be written without superscripts? I'm not referring to the specific proof technique known as relativization, but just to the general concept of a complexity class being relative to an oracle machine. $\endgroup$ – tparker Aug 23 '16 at 23:57
  • 1
    $\begingroup$ Check whether my edit accurately captures what you had in mind. $\endgroup$ – D.W. Aug 24 '16 at 0:06
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.