Raz, Ran; McKenzie, Pierre Separation of the monotone NC hierarchy. (English) Zbl 0977.68037 Combinatorica 19, No. 3, 403-435 (1999). The class monotone-\(NC^i\) is the class of all functions that can be computed by polynomial-size circuits of depth \(O(\log^in)\) over the monotone base \(\{\wedge,\vee\}\). It is shown that, for all \(i\), monotone-\(NC^i\) is a strict subclass of monotone-\(NC^{i+1}\), and, thus, monotone-\(NC\), the union of the classes monotone-\(NC^i\) over all \(i\), is a strict subclass of monotone-\(P\). This substantially improves the only previously known separation of monotone-\(NC^1\) from monotone-\(NC^2\). Additionally, more general results, for arbitrary bounds \(D(n)\) below \(n^\varepsilon\), are obtained. Further consequences address the complexity of two particular problems: st-connectivity and \(k\)-clique. The proof of the main result relies on a communication theoretic argument, for which a new class of games, so called DART games, are introduced. Reviewer: Heribert Vollmer (Würzburg) Cited in 8 ReviewsCited in 38 Documents MSC: 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R99 Discrete mathematics in relation to computer science 68Q25 Analysis of algorithms and problem complexity Keywords:monotone circuits; monotone-NC; communication complexity PDFBibTeX XMLCite \textit{R. Raz} and \textit{P. McKenzie}, Combinatorica 19, No. 3, 403--435 (1999; Zbl 0977.68037) Full Text: DOI