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