Circuits over PP and PL
R. Beigel, Bin Fu · 2002
C.B. Wilson's (1985) 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 previous authors, we prove that PL and PP are closed under NC/sub 1/ reductions. This answers an open problem of M. Ogihara (1996). More generally, we show that NC/sub k+1//sup PP/=AC/sub k//sup PP/ and NC/sub k+1//sup PL/=AC/sub k//sup PL/ for all k/spl ges/0. On the other hand, we construct an oracle A such that NC/sub k/(PP/sup A/)/spl ne/NC/sub k+1/(PP/sup A/) for all integers k/spl ges/1. Slightly weaker than NC/sub 1/ reductions are Boolean formula reductions. We ask whether PL and PP are closed under Boolean formula reductions. This is a nontrivial question despite NC/sub 1/=BF, because that equality is easily seen not to relativize. We prove that P/sub log2n/loglogn-T//sup PP//spl sube/BF/sup PP//spl sube/PrTIME(n/sup O(logn)/). Because P/sub log2n/loglogn-T//sup PP//spl nsub/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.