There is a great but little-known theorem from the early 90's by Seinosuke Toda and Mitsunori Ogihara (buried as Lemma 2.3 in their paper) that shows the polynomial-time hierarchy is randomly low for Gap-P.
Let M be a non-deterministic polynomial-time machine. #M(x) is the number of accepting paths of M on x. #P is the set of functions f such that f(x) = #M(x) for an NP machine M.
Gap-M(x) is the difference between the number of accepting and rejecting paths. Unlike #M(x), Gap-M(x) could be negative. Gap-P is the set of functions such that f(x)=Gap-M(x) for an NP machine M. Equivalently Gap-P is the difference of two #P functions. Gap-P inherits all the nice closure properties of #P while being closed under negation and subtraction.
Theorem (Toda-Ogihara): Let q be a polynomial and f be a function in Gap-PPH. There is a function g in Gap-P and a polynomial p such that for all x, if you choose a binary string r randomly of length p(|x|), f(x) = g(x,r) with probability at least 1-2-q(|x|).
In other words, with randomness the PH as an oracle of Gap-P disappears.
Let me show you how the proof works for a specific f in GapPPH, namely the indicator function for SAT: f(φ) = 1 if φ is satisfiable and 0 otherwise.
Recall Valiant-Vazirani showed how to randomly reduce a formula φ to a set of formula ψ1,…,ψk such that
- If φ is not satisfiable then for all i, ψi will not be satisfiable
- If φ is satisfiable then with high probability for some i, ψi will have exactly one satisfying assignment.
- If φ is not satisfiable then for all i, #ψi=0 and g(φ,r) = 0.
- If φ is satisfiable then with high probability for some i, #ψi=1 and thus g(φ,r) = 1.