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