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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
Язык <tex>A</tex> является <tex>NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex>NL</tex> и любой другой язык <tex>A'</tex> из <tex>NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.
 
Язык <tex>A</tex> является <tex>NL</tex>-полным ('''NLC'''), если он принадлежит классу <tex>NL</tex> и любой другой язык <tex>A'</tex> из <tex>NL</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.
  
Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык <tex>A'</tex> из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.  
+
Язык ''A'' является '''NL'''-полным ('''NLC'''), если он принадлежит классу '''NL''' и любой другой язык ''A<nowiki>'</nowiki>'' из '''NL''' можно [[сведение по Карпу|свести по Карпу]] к ''A'', притом сведение будет использовать логарифмическое количество памяти.  
 
То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
 
То есть сведение не может сохранить входные данные, но может неограниченно писать на выходную ленту и читать со входной.
  

Версия 18:29, 8 апреля 2010

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

Определение

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

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

Теорема

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

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

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

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

Используя логарифмическое количество памяти B сводится к языку A, который уже лежит в L.

Тонкость состоит в том, что мы не можем сохранить

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

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