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