31
правка
Изменения
Нет описания правки
}}
'''Следствие:''' <tex>NC = AC</tex><br/>
|proof =
Пусть <tex>L \in NC</tex>. Тогда <tex>L</tex> распознается некоторым семейством схем <tex>C_n</tex> которые по <tex>1^n</tex> можно построить на <tex>O(log(n))</tex> памяти и, следовательно, за полиномиальное от <tex>n</tex> время. Построим для данного входа схему и вычислим ее.}}
{{Теорема
|statement=
<tex>L</tex> распознается параллельным компьютером с <tex>O(poly(n))</tex> процессоров за время <tex>O(poly(log(n)) \Leftrightarrow L \in NC</tex>.
}}
