Circuits over PP and PL

摘要

Wilson's (1985, J. Comput. System. Sci.31, 169–181) model of oracle gates provides a framework for considering reductions whose strength is intermediate between truth-table and Turing. Improving on a stream of previously published results, we prove that PL and PP are closed under NC1 reductions. This answers an open problem of Ogihara (1996, “Proc. 37th Ann. IEEE Symp. Found. Computer Sci.”). More generally, we show that NCPPk+1=ACPPk and NCPLk+1=ACPLk for all k⩾0. On the other hand, we construct an oracle A such that NCPPAk≠NCPPAk+1 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 PPPlog2 n/log log n−T⊆BFPP⊆PrTIME(nO(log n)). Because PPPlog2 n/log log n−T⊈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.