On the decomposability of NC and AC. (English) Zbl 0692.68045

Wilson, Christopher B.

SIAM J. Comput. 19, No. 2, 384-396 (1990).

Summary: It is shown for rationals a,b\(\geq 1\) that \(NC_ a^{NC_ b}=NC_{a+b- 1}\). As a consequence, if, for some \(k\geq 1\) and \(\epsilon >0\), \(NC_ k=NC_{k+\epsilon}\), then \(NC_ k=NC\). A similar development can be applied to circuits with unbounded fan-in. It is seen that \(AC_ a^{AC_ b}=AC_{a+b}\), \(AC_ a^{NC_ b}=NC_{a+b}\) and \(NC_ a^{AC_ b}=AC_{a+b-1}\). This shows for \(a\geq 0\) and \(b\geq 1\) that \(AC_ a^{AC_ b}=NC_{a+1}^{AC_ b}\) and \(AC_ a^{NC_ b}=NC_{a+1}^{NC_ b}\). An oracle A is constructed for which \(\forall k\), \(NC^ A_ k\subset AC^ A_ k\) and, in fact, \(AC^ A_ k-NC^ A_{k+\epsilon}\neq \emptyset\) for any \(\epsilon <1\). Similarly, there is an A so that \(\forall k\) and \(\epsilon <1\), \(NC^ A_{k+1}-AC^ A_{k+\epsilon}\neq \emptyset\), and hence \(AC^ A_ k\subset NC^ A_{k+1}\). Combining, this yields an A such that, for all k and \(0<\epsilon <1\), the classes \(AC^ A_ k\) and \(NC^ A_{k+\epsilon}\) are incomparable.

MSC:

68Q25	Analysis of algorithms and problem complexity
03D15	Complexity of computation (including implicit computational complexity)

Keywords:

parallel complexity classes; relativization; NC; AC; circuits; oracle