NL-полнота — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 10 промежуточных версий 5 участников)
Строка 3: Строка 3:
 
===Определение===
 
===Определение===
  
Язык <tex>A</tex> является <tex>NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex>NL</tex> и любой другой язык <tex>A'</tex> из <tex>NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.
+
Язык <tex>A</tex> является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex>A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.  
 
 
Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык ''A<nowiki>'</nowiki>'' из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к ''A'', притом сведение будет использовать логарифмическое количество памяти.  
 
 
То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
 
То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
  
Строка 14: Строка 12:
 
===Доказательство===
 
===Доказательство===
  
Рассмотрим язык ''B'' <tex>B</tex> из класса '''NL'''.  
+
Рассмотрим язык <tex>B</tex> из класса '''NL'''.  
Для каждого слова ''x'' <tex>x</tex> необходимо определять его принадлежность ''B'' используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти.
+
Для каждого слова <tex>x</tex> необходимо определять его принадлежность <tex>B</tex> используя лишь детерминированные выборы и ''O''(log ''n'') дополнительной памяти.
 
 
Так как ''A'' '''NL'''-полон, то существует такая функция ''f'' <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>.
 
  
Используя логарифмическое количество памяти ''B'' сводится к языку ''A'', который уже лежит в '''L'''.
+
Так как <tex>A</tex> '''NL'''-полон, то существует такая функция <tex>f</tex> (использующая ''O''(log ''n'') дополнительной памяти), что <tex>x \in B \Leftrightarrow f(x) \in A</tex>.
 +
<tex>A</tex> принадлежит '''L''', поэтому мы можем определить принадлежность <tex>x</tex> языку <tex>B</tex> с необходимыми условиями.
  
Тонкость состоит в том, что мы не можем сохранить  
+
Однако, результат работы функции <tex>f</tex> сохранить невозможно, так как он может занимать более ''O''(log ''n'') памяти.
 +
Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции (который запрашивает детерминированная машина Тьюринга, соответствующая языку <tex>A</tex>, для определения истинности <tex>f(x) \in A</tex>) будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.
  
 
==Примеры NL-полных задач==
 
==Примеры NL-полных задач==
  
 
[[NL-полнота задачи о достижимости в графе]]
 
[[NL-полнота задачи о достижимости в графе]]
 +
 +
[[2-SAT]]
 +
 +
[[Категория:Классы сложности]]

Текущая версия на 11:44, 1 сентября 2022

В классе NL выделяют подкласс полных в этом классе задач.

Определение

Язык [math]A[/math] является NL-полным (NLC), если он принадлежит классу NL и любой другой язык [math]A'[/math] из NL можно свести по Карпу к [math]A[/math], притом сведение будет использовать логарифмическое количество памяти. То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.

Теорема

Если в классе L существует такой язык [math]A[/math], что он NL-полон, то NL = L.

Доказательство

Рассмотрим язык [math]B[/math] из класса NL. Для каждого слова [math]x[/math] необходимо определять его принадлежность [math]B[/math] используя лишь детерминированные выборы и O(log n) дополнительной памяти.

Так как [math]A[/math] NL-полон, то существует такая функция [math]f[/math] (использующая O(log n) дополнительной памяти), что [math]x \in B \Leftrightarrow f(x) \in A[/math]. [math]A[/math] принадлежит L, поэтому мы можем определить принадлежность [math]x[/math] языку [math]B[/math] с необходимыми условиями.

Однако, результат работы функции [math]f[/math] сохранить невозможно, так как он может занимать более O(log n) памяти. Но ограничение по времени отсутствует, поэтому для определения некоторого элемента результата работы функции (который запрашивает детерминированная машина Тьюринга, соответствующая языку [math]A[/math], для определения истинности [math]f(x) \in A[/math]) будем просто перезапускать функцию и запоминать лишь необходимый элемент ее результата.

Примеры NL-полных задач

NL-полнота задачи о достижимости в графе

2-SAT