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