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 intermedi ate between truth-table and Turing. Improving on a stream of previously pub lished results. we prove that PL and PP are closed under NC1 reductions. Th is answers an open problem of Ogihara (1996. "Proc. 37th Ann. IEEE Symp. Fo und. Computer Sci."). More generally, we show that NCk + 1 (PP) = AC(k) (PP ) and NCk + 1 (PL) = AC(k) (PL) for all k greater than or equal to 0. On th e other hand, we construct an oracle A such that NCk (PPA) not equal NCk 1 (PP1) for all intergers k greater than or equal to 1. Slightly weaker tha n NC, reductions are Boolean formula reductions. We ask whether PL and PP a re closed under Boolean formula reductions. This is a nontrivial question d espite NC1 = BF, because that equality is easily seen not to relativize. We prove that P-log(2) (- n log log n -T) (PP) subset of or equal to BFPP sub set of or equal to PrTIME(n(O(log n))). Because P-log(n/log log n-T)2 (PP) not subset of or equal to PP relative to an oracle, we think it is unlikely that PP is closed under Boolean formula reductions. We also show that PL i s unlikely to be closed under BF reductions. (C) 2000 Academic Press.