editor
143
правки
Изменения
Нет описания правки
{{Определение
|definition='''Класс <tex>L</tex>''' — множество языков, разрешимых на детерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.
<tex>L = \mathrm{DSPACE}(O(\log n))</tex>
}}
{{Определение
|definition='''Класс <tex>\mathrm{NL}</tex>''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием <tex>O(\log n)</tex> дополнительной памяти для входа длиной <tex>n</tex>.<tex>NL = \mathrm{NSPACE}(O(\log n))</tex>
}}
