Изменения

|statement=<tex>\mathrm{NC^i} \subset \mathrm{AC^i} \subset \mathrm{NC^{i+1}}</tex>.

|statement=<tex>\mathrm{NC} \subseteq \mathrm{P}</tex>.

Пусть <tex>L \in \mathrm{NC}</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex>, таких, что существует детерминированная машина Тьюринга, строящая такую схему по <tex>1^n</tex>, используя <tex>O(log(n))</tex> ячеек памяти. Конфигурация МТ задается положением головки и состоянием ячеек памяти, то есть у МТ может быть <tex>n \cdot 2^{O(log(n))} = O(n^2)</tex> конфигураций. При построении схемы конфигурации не могут повторяться, иначе МТ зациклится, следовательно схема будет построена за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим еееё. На вычисление схемы потребуется полином временибудет затрачено полиномиальное время, так как схема полиномиального размераразмер схемы полиномиален.}}