The results given here are very pretty. They relate the power of different circuit-based notions of reducibility. In particular, Wilson shows how the NC and AC hierarchies can be decomposed in a manner reminiscent of the decomposition of the polynomial hierarchy via NP-Turing reducibility.
Earlier work by other authors established the utility of NC1 reducibility and constant-depth reducibility. In this paper, Wilson considers more general NCa and ACa reducibilities computed by either bounded or unbounded fan-in circuits of polynomial size and depth O ( log a n ) for any rational number a greater than or equal to 0. These are “Turing-like” reductions: the circuits are equipped with oracle gates.
The main results are that, for all rational numbers a and b greater than or equal to 1, NC aNCb = NC a + b - 1 and AC aACb = NC a + b . A number of interesting corollaries follow; for instance, AC aC = NC a + 1C whenever C is a set of the form ACb or NCb. (This result has recently been generalized to a richer set of classes C [1].) Another application yields the implication NC a = NC a + &egr; ⟹ NC = NC a. Wilson also presents some oracle constructions, indicating obstacles that must be overcome if known relationships among the levels of the NC hierarchy are to be improved.
