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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Определение)
(→‎Определение)
Строка 4: Строка 4:
 
Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathbf{NL}</tex>-полным (<tex dpi="100">\mathbf{NLC}</tex>), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathbf{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
 
Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathbf{NL}</tex>-полным (<tex dpi="100">\mathbf{NLC}</tex>), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathbf{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
  
−
Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathrm{NL}</tex>-полным (<tex dpi="100">\mathrm{NLC}</tex>), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathrm{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
+
Язык <tex>A</tex> является <tex>\mathrm{NL}</tex>-полным (<tex>\mathrm{NLC}</tex>), если он принадлежит классу <tex>\mathrm{NL}</tex> и любой другой язык <tex>A'</tex> из <tex>\mathrm{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex>A</tex>, притом сведение будет использовать логарифмическое количество памяти.
 +
 
 +
Язык <tex dpi="100">A</tex> является <tex dpi="100">\mathrm{NL}</tex>-полным (<tex dpi="100">\mathrm{NLC}</tex>), если он принадлежит классу <tex dpi="100">\mathrm{NL}</tex> и любой другой язык <tex dpi="100">A'</tex> из <tex dpi="100">\mathrm{NL}</tex> можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
  
 
Язык <tex dpi="100">A</tex> является NL-полным (NLC), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из NL можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.
 
Язык <tex dpi="100">A</tex> является NL-полным (NLC), если он принадлежит классу NL и любой другой язык <tex dpi="100">A'</tex> из NL можно [[сведение по Карпу|свести по Карпу]] к <tex dpi="100">A</tex>, притом сведение будет использовать логарифмическое количество памяти.

Версия 19:14, 8 апреля 2010

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

Определение

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

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

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

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

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

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

Язык [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-полнота задачи о достижимости в графе

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=NL-полнота&oldid=729»