Класс NL — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга …»)
 
Строка 1: Строка 1:
Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной ''n''.
+
Класс языков '''NL''' — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием ''O''(log ''n'') дополнительной памяти для входа длинной ''n''.
 +
 
 +
Используя определение '''[[Класс NSPACE|NSPACE]]''' можно формализовать определение: NL = '''NSPACE'''(log ''n'').

Версия 16:12, 7 апреля 2010

Класс языков NL — множество языков, разрешимых на недетерминированной машине Тьюринга с использованием O(log n) дополнительной памяти для входа длинной n.

Используя определение NSPACE можно формализовать определение: NL = NSPACE(log n).