65
$\begingroup$

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were given to the contrary, and on the other Scott suggested that the answer is likely positive since Toda's theorem shows that PH is in BP.PP, the probabilistic variant of PP, and we usually believe that randomization does not help much, e.g. reasonable hardness assumptions implies PRGs which can replace randomization.

Now, in the case of PP it is not apriori clear that even a "perfect" PRG will imply complete derandomization since the natural derandomization would run the original algorithm with the output of the PRG for all polynomially-many possible seeds and take a majority vote. It it is not clear that taking that majority vote among PP computations is something that can be done in PP itself. However, a paper by Fortnow and Reingold shows that PP is closed under truth-table reductions (extending the surprising result that PP is closed under intersection), which seems to suffice for taking this majority vote.

So what is the question here? Toda, Fortnow-Reingold and all the PRG-based derandomizations, all seem to relativize, so would imply that PH in PP for every oracle for which appropriate PRGs exist. So for all the oracles under which PP does not contain PH (e.g. from Minski&Papert, by Beigel, or by Vereshchagin), PRGs for PP do not exist. In particular this implies that for these oracles there are no appropriately hard functions in EXP (otherwise NW-IW-like PRGs would exist). Looking at the positive side, this would imply that somewhere inside each of these oracle results hides a (non-uniform) PP-algorithm for (approximating) EXP with that oracle. This is strange since all these oracle results seem to rely on new PP lower bounds (for threshold circuits) and are straight-forward in their oracle-building machinery, so I don't see where an upper bound for PP hides. Perhaps this upper bound would work in general showing that (non-uniform)-PP can compute (or at least give some bias on) all of EXP? Wouldn't something like that give at least a CH simulation of EXP?

So, I suppose that my question is two-fold: (1) does this chain of reasoning make sense? (2) If so, then can someone "uncover" the implied upper bounds for PP?

Edit by Aaron Sterling: bumping this to the front page and adding a bounty. This was one of my favorite questions, and it still has no answers.

Improve this question
$\endgroup$
15
  • 2
    $\begingroup$ Indeed start with a Boolean function $f:\{0,1\}^N \rightarrow \{ 0,1\}$ in AC0 that cannot be computed by a polylog(N)-degree threshold gate. For each oracle $A$ we define the language $L_A= \{1^n | f(A_n)=1\}$ (where $A_n$ is the $2^n$ bits of the $n$'th slice of $A$). Since $f \in AC0$, $L_A \in PH^A$, for all $A$. The $t$'th diagonalization step will choose $A_n$ (for some $n$) such that the $t$'th PP TM makes a mistake on $1^n \in L_A?$, which happens since $f$ is not polylog(N)-threshold (as a PP machine's computation is). So $L_A \not\in PP^A$. But maybe $L_A \in PP^A|poly$... $\endgroup$
    – Noam
    Nov 29, 2010 at 9:12
  • 2
    $\begingroup$ So to get also $L_A \not\in PP^A/poly$ we would need to pack many instances of $f$ into a single length $n$. This seems easily doable by defining $L_A = \{ x | f(A_x)=1\}$, where for an $n$-bit string $x$,$A_x$ denotes the $2^n$-bits describing whether $xy \in A$ for all $2^n$ possible $y$'s of length $n$. But we would need to improve the lower bound for $f$ to require that $N$ copies of $f$ on different $N$-bit strings cannot be computed by polylog(N)-degree threshold gates, even with polylog(N) help bits. So this should be false for any $f \in AC0$. An interesting upper bound it seems. $\endgroup$
    – Noam
    Nov 29, 2010 at 9:29
  • 1
    $\begingroup$ Come to think of it, the observation that under every oracle that makes PH /⊆ PP there are no efficient PRGs that fool BP.PP algorithms should not be any more surprising than the fact that under every oracle that makes BPP /⊆ P there are no efficient PRGs that fool BPP algorithms. That's because every oracle that makes PH /⊆ PP also makes BP.PP /⊆ PP by Toda's theorem (relativized). But maybe I am missing the point. – $\endgroup$
    – slimton
    Dec 1, 2010 at 20:35
  • 1
    $\begingroup$ That's a good point. However, intuitively when you make an oracle for which $P^A \ne BPP^A$ the crux of the construction is giving some unusual power to $BPP^A$, so that implies unusual power to $P^A/poly$ too and thus makes PRGs impossible. The oracle for $PH^A \not\subseteq PP^A$ does not seem to give any unusual power to $P^A$ (or to any class) but rather to limit the power of $PP^A$. I'm not sure however whether this difference can be formalized somehow. $\endgroup$
    – Noam
    Dec 2, 2010 at 19:42
  • 1
    $\begingroup$ As I remarked above: in the constructions for $P \ne BPP$ the crux of the construction is giving "un-natural" power to BPP (and thus also to P/poly) by e.g. planting lots of witnesses for the hard oracle in places where only randomization can find them. So while it is indeed interesting that this power suffices for "general" problems at least the unexpected power of P/poly is clear. On the other hand, I can't see anywhere that the oracle for separating PH from PP gives un-natural power to P/poly or any other class, in fact. I'm not sure that this difference is "real" though. $\endgroup$
    – Noam
    Dec 7, 2010 at 19:19

1 Answer 1

Reset to default
11
$\begingroup$

By the work of Klivans and van Melkebeek (which relativizes), if E = DTIME($2^{O(n)}$) does not have circuits with PP gates of size $2^{o(n)}$ then PH is in PP. The contrapositive says that if PH is not in PP then E has subexponential-size circuits with PP gates. That is consistent with the fact that an oracle proof of PH not in PP gives a relativized lower bound for PP. No reason to think it implies any upper bound for PP, or any strength for circuits without PP gates.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Correct. Fixed. $\endgroup$
    – Lance Fortnow
    Mar 6, 2016 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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