Изменения

Перейти к: навигация, поиск

Классы L, NL, coNL

4 байта добавлено, 15:39, 14 марта 2013
Нет описания правки
{{ Теорема
| statement = <tex>\mathrm{L} \subset subseteq \mathrm{NL} \subset subseteq \mathrm{NP}.</tex>
| proof =
#Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \subset \mathrm{NL}</tex>.
#Число конфигураций машины, использующей <tex>O(\log n)</tex> памяти не превышает <tex>2^{O(\log n)} = n^{O(1)} = poly(n)</tex>, а, следовательно, если машина завершает свою работу, то она это делает за <tex>O(poly(n))</tex> времени. Следовательно, <tex>\mathrm{NL} \subset \mathrm{P}.</tex>
}}
editor
143
правки

Навигация