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