Conceptio › Archive › Stack Exchange
Stack Exchange open access CC BY-SA

More on PH in PP?

Noam · 2010
Stack Exchange · Datasets · License: CC BY-SA · 2010
Open Source ↗
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
Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

This document is indexed with metadata only: full text is not available in the archive for this record. Open the official source ↗

Related documents

Record · ID 787540
Retrieved via Conceptio: every document is proof-bundled with source, license, and retrieval metadata.
Bring this data into your agent: Connect via MCP or API · 20 free credits to start · no card required
Read the Docs → · View CLI source on GitHub · Conceptio Open Knowledge Archive