**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_{1} 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_{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_{1} =
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.