Классы L, NL, coNL — различия между версиями
Строка 18: | Строка 18: | ||
| proof = | | proof = | ||
#Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <tex>\mathrm{L} \subset \mathrm{NL}</tex>. | #Детерминированная машина Тьюринга есть частный случай недетерминированной, поэтому <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{ | + | #Число конфигураций машины, использующей <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{NP}.</tex> |
}} | }} |
Версия 16:07, 14 марта 2013
Определение: |
Класс | — множество языков, разрешимых на детерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной . .
Определение: |
Класс | — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием дополнительной памяти для входа длиной . .
Определение: |
Класс . | — множество языков, дополнение до которых принадлежит .
Теорема: |
Доказательство: |
|