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