Изменения

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

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