Separation of the monotone NC hierarchy (Q1977414)

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.