Title: Circuits over PP and PL

Authors: Richard Beigel and and Bin Fu

Abstract: Wilson's (JCSS '85) model of oracle gates provides a framework for considering reductions whose strength is intermediate between truth-table and Turing. Improving on a stream of results by Beigel, Reingold, Spielman, Fortnow, and Ogihara, we prove that PL and PP are closed under NC1 reductions. This answers an open problem of Ogihara (FOCS '96). More generally, we show that NCk+1PP = ACkPP and NCk+1PL = ACkPL for all k ≥ 0. On the other hand, we construct an oracle A such that NCkPPA ≠ NCk+1PPA for all integers k ≥ 1.

Slightly weaker than NC1 reductions are Boolean formula reductions. We ask whether PL and PP are closed under Boolean formula reductions. This is a nontrivial question despite NC1 = BF, because that equality is easily seen not to relativize. We prove that PPPlog²n/loglogn-T ⊆ BFPP ⊆ PrTIME(nO(logn)). Because PPPlog²n/loglogn-T is not contained in PP relative to an oracle, we think it is unlikely that PP is closed under Boolean formula reductions. We also show that PL is unlikely to be closed under BF reductions.

Download Full Paper