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 ψ_{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.

^{-q(|x|)}. Let g(φ,r) use r to choose ψ

_{1},…,ψ

_{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.

Does derandomization of Valiant Vazirani derandomize the full result or only this example?

ReplyDeleteGreat question. The proof of the full Toda-Ogihara result requires a version of Valiant-Vazirani relative to the polynomial-time hierarchy and thus a stronger derandomization assumption. An assumption like DTIME(2^n) not in DSPACE(2^{o(n)}) will give you a PRG sufficient to fully derandomize Toda-Ogihara.

DeleteCan there be a converse such as deterministic Toda-Ogihara implies the time space separation? Or is it possible results such as EXP in PSPACE abd deterministic Toda-Ogihara are both simultaneously possible as far as we know?

ReplyDeleteProbably not a full converse but it would be interesting to see if there is some circuit lower bound one could obtain from a deterministic version of Toda-Ogihara. I'll leave that as an open question.

DeleteWhile on the question of derandomizing [VV85], here is a fine question: Is there a Pseudo-deterministic RP reduction from SAT to USAT, i.e., the reduction can use random bits but reruns of the reduction should produce the same instance of USAT with very high probability.

ReplyDelete