Изменения

<tex>\mathrm{NC^i}</tex>— множество языков, которые распознаются семейством логических схем размера полином от <tex>n</tex> и глубины <tex>O(log^i (n))</tex>, где <tex>n</tex> — длина входа; степень входа элемента не больше двух. Причем существует детерминированная машина Тьюринга, строящая такую схему по <tex>1^n</tex>, используя <tex>O(log(n))</tex> ячеек памяти.

<tex>\mathrm{AC^i}</tex> определяется аналогично <tex>\mathrm{NC^i}</tex>, только степень входа элемента неограничена.

<tex>\mathrm{NC } = \bigcup \limits_{i = 0}^{\infty} \mathrm{NC^i}</tex><br/><tex>\mathrm{AC } = \bigcup \limits_{i = 0}^{\infty} \mathrm{AC^i}</tex><br/>