The hierarchy and GapP

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-P^PH. 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 GapP^PH, 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 ψ₁,…,ψ_k such that

1. If φ is not satisfiable then for all i, ψ_i will not be satisfiable
2. If φ is satisfiable then with high probability for some i, ψ_i will have exactly one satisfying assignment.

Picking k > 4|x|q(|x|) will reduce the error in (2) to under 2^-q(|x|). Let g(φ,r) use r to choose ψ₁,…,ψ_k and output the Gap-P function 1-∏(1-#ψ_i) using the closure properties of Gap-P where #ψ_i is the number of satisfying assignments to ψ_i.

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

Note that if r is a bad random sequence and φ is satisfiable, g(φ,r) might be an exponentially large integer, positive or negative. It's right most of the time but when it's wrong it's terribly wrong.