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