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 NC₁ reductions. This answers an open problem of Ogihara (FOCS '96). More generally, we show that NC_k+1^PP = AC_k^PP and NC_k+1^PL = AC_k^PL for all k ≥ 0. On the other hand, we construct an oracle A such that NC_k^PPA ≠ NC_k+1^PPA for all integers k ≥ 1.

Slightly weaker than NC₁ reductions are Boolean formula reductions. We ask whether PL and PP are closed under Boolean formula reductions. This is a nontrivial question despite NC₁ = BF, because that equality is easily seen not to relativize. We prove that P^PP_{log²n/loglogn-T} ⊆ BF^PP ⊆ PrTIME(n^O(logn)). Because P^PP_{log²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