65

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.

Community
  • 1
Noam
  • 9,369
  • 47
  • 58
  • The line of reasoning make sense to me. Is it possible to describe in a few words the oracle that makes PH not be in PP? If I were to build it I would start with a Boolean function in AC$^0$ that cannot be represented by the sign of a polynomial of low degree and scale it up to the oracle. But wouldn't that also give an oracle were PH is not in PP/poly and hence not in BP.PP? (the inclusion BP.PP in PP/poly would be using amplification via the closure of PP under tt-reductions). – slimton Nov 29 '10 at 06:24
  • 2
    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$... – Noam Nov 29 '10 at 09:12
  • 2
    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. – Noam Nov 29 '10 at 09:29
  • I see. So the reason that the straightforward oracle making PH$^A$ $\not\subseteq$ PP$^A$ does not also make PH$^A$ $\not\subseteq$ PP$^A$/poly is that a non-uniform family of polylog-degree threshold circuits is seemingly weaker than a log-scaled PP$^A$/poly algorithm on tally inputs. – slimton Nov 30 '10 at 07:33
  • 1
    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. – – slimton Dec 01 '10 at 20:35
  • 1
    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. – Noam Dec 02 '10 at 19:42
  • Now that the bounty is gone, I'd like to try an answer in the form of a question: Isn't the same question relevant to the oracle that makes BPP $\not\subseteq$ P? In other words, in a world where BPP $\not\subseteq$ P there are no pseudorandom generators that fool BPP algorithms, which means that all of E (with that oracle) has subexponential-size circuits (with that oracle). Question is: Where is the hidden upper bound? Adapting your own phrasing: "Looking at the positive side, this would imply that somewhere inside each of these oracle results hides a (non-uniform) subexponential algorithm – slimton Dec 07 '10 at 14:10
  • for (approximating) E with that oracle. This is strange since all these oracle results [...] are straight-forward in their oracle-building machinery, so I don't see where an upper bound hides."

    Perhaps the answer is that the oracle-building machinery is not that straight-forward after all (in other words, diagonalization is powerful).

     – slimton Dec 07 '10 at 14:10
  • 1
    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. – Noam Dec 07 '10 at 19:19
  • I'm sorry I didn't see your remark above. It was hidden under the fold. I'll think of it. – slimton Dec 08 '10 at 18:05
  • It was shown by Toda that PH ⊆ BP . Parity-P NOT PH ⊆ BP. PP I believe there is a misunderstanding... – Tayfun Pay Aug 04 '11 at 01:15
  • Can someone link the proof of PH in BP.PP? Thanks – Tayfun Pay Nov 09 '11 at 04:26
  • 1
    @Tayfun Pay: As far as I can tell, it first appeared in Toda and Ogiwara, Counting Classes are at Least as Hard as the Polynomial Time Hierarchy. – Aaron Sterling Nov 13 '11 at 00:09
  • @Aaron Awesome! However, I cannot access it. Do you know where I can get a copy of it? Thank you so much! :) – Tayfun Pay Nov 15 '11 at 03:49
  • 1
    @Tayfun Pay: I don't. Ogiwara is a professor at Rochester I think, so you might consider emailing him directly. I have thought about writing a blog entry sketching the proof that Toda's Theorem implies PH is in BP.PP, but I am getting slammed right now, so I am not sure I will get to it. I looked for a self-contained proof on the web, and was not able to find one. – Aaron Sterling Nov 15 '11 at 23:15

1 Answers1

11

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.

Lance Fortnow
  • 8,681
  • 44
  • 59