Изменения

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

Классы L, NL, coNL

798 байт добавлено, 20:41, 4 июня 2012
Новая страница: «{{Определение |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>.
}}
editor
143
правки

Навигация