Класс NL — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Соотношения между классами)
(не показаны 3 промежуточные версии 2 участников)
Строка 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]]''', так как было доказано, что задача '''[[2-SAT]]''' [[NL-полнота|NL-полна]].
+
Класс '''NL''' является подмножеством класса '''[[P]]''', так как число конфигураций машины, использующей ''O''(log&nbsp;''n'') памяти не превышает 2<sup>''O''(log&nbsp;''n'')</sup>&nbsp;=&nbsp;''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''' совпадают.

Версия 16:20, 15 апреля 2010

Класс языков 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 совпадают.