Теорема Левина — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 19 промежуточных версий 6 участников)
Строка 1: Строка 1:
−
По одному из определений <math>NP</math> языка, язык <math>L</math> принадлежит <math>NP</math>, если существует такая функция <math>R(x, y) \in \tilde{P}</math> — <math>NP</math>-отношение для языка <math>L</math> (<math>NP</math>-relation), что: <math>x \in L \Leftrightarrow \exists y</math> — такой сертификат для <math>x</math>, что: <math>|y| \le poly(|x|)</math> и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет, и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
+
{{Теорема
 +
|author=Левин
 +
|statement=
 +
Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определения <tex>\Sigma_1</tex>) отношения <tex>R</tex> существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <tex>p</tex>, сопоставляющая словам из <tex>L</tex> их сертификаты, то есть:
 +
# <tex>x \in L \Leftrightarrow R(x, p(x)) = 1</tex>;
 +
# для любой другой программы <tex>q</tex>, для которой верно <tex>x \in L \Leftrightarrow R(x, q(x)) = 1</tex>, найдутся такие константа <tex>c</tex> и полином <tex>r</tex>, что для любого <tex>x</tex> выполняется: <tex>T(p, x) \le c \cdot T(q, x) + r(|x|)</tex>.
 +
|proof=
 +
Построим «оптимальную» программу <tex>p(x)</tex>.
  
−
Встает вопрос о возможности построения "оптимальной" программы для заранее заданного NP языка L и NP-отношения для этого языка R, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.
+
Пронумеруем все программы <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Подадим им на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-1}</tex> и не делится на <tex>2^{k}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге начиная с <tex>2^{k-1}</tex>-го. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>2^{k-1} + (T(P_k, x) - 1) \cdot 2^k</tex> шагов.
  
−
== Формулировка ==
+
Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу, ничего не делая на тех шагах, когда должна была исполняться <tex>p_k</tex>.
−
'''Теорема Левина об оптимальной NP программе''' утверждает, что для любого языка <math>L \in NP</math> и функции <math>R</math> (<math>NP</math>-отношения для <math>L</math>) существует такая программа <math>f</math>, что:
 
−
#<math>\forall x \in L</math> выполнено <math>R(x, f(x)) = 1</math>;
 
−
#<math>\forall g</math> — такой программы, что <math>\forall x \in L: R(x, g(x)) = 1</math> выполнено <math>\forall x \in L: T(f, x) \le C(g) \cdot (T(g, x) + poly(|x|))</math>, где T(f, x) — время работы программы f на входе x.
 
  
−
Заметим, что функция C(g) не зависит от слова х, т.е. константа от х.
+
Таким образом, если некоторая программа <tex>q = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{m-1} + (T(p_m,x) + T(R, \langle x,p_m(x) \rangle) - 1) \cdot 2^m</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{m-1} + (T(p_m,x) + poly(|x|)) \cdot 2^m = 2^m \cdot T(q,x) + poly(|x|)</tex>.
 +
}}
  
−
== Доказательство ==
+
== См. также ==
−
Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для него.
+
*[[Класс P]]
 +
*[[Классы_NP_и_Σ₁]]
  
−
Занумеруем все программы <math>g_1, g_2, ... , g_n, ...</math> сначала по длине программы, а в случае равенства длин — лексикографически.
+
[[Категория: Теория сложности]]
−
 
 
−
Будем запускать <math>g_i</math> каждый раз на один шаг и запоминать полученное состояние запущенной программы. Запускать будем в следующем порядке: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 и так далее. Заметим, что мы запускаем программу <math>g_i</math> каждый <math>2^i</math>-й раз, а потому, если программа <math>g_i(x)</math> завершается за <math>k</math> шагов, то <math>f</math> совершит не больше <math>2^i \cdot k</math> шагов до момента завершения <math>g_i</math> на входе <math>x</math> в программе <math>f</math>.
 
−
 
 
−
После того, как программа <math>g_i</math> остановилась, на её месте будем запускать программу <math>R(x, y)</math>, где <math>y</math> - значение, которое вернула <math>g_i(x)</math>. Причем f совершит не больше <math>2^i \cdot poly(|x + y|)</math> шагов до завершения программы <math>R(x, y)</math>, так как <math>R \in \tilde{P}</math> и она запускается каждый <math>2^i</math>-й раз. Если <math>R(x, y)</math> вернула <math>true</math>, то возвратим <math>y</math>, так как <math>y</math> — нужный сертификат для <math>x</math>, а если <math>false</math>, то ничего на этом месте больше запускать не будем.
 
−
 
 
−
Осталось доказать, что данная программа действительно удовлетворяет пунктам 1 и 2 теоремы Левина.
 
−
#Так как программа f возвращает только те у, для которых R(x, y) = 1, то R(x, f(x)) = 0 получиться не может. Покажем, что и зависнуть на словах из языка <math>f</math> не может. Как выше уже упоминалось, если слово принадлежит языку <math>L</math>, то для него есть сертификат, а значит есть и программа <math>g</math>, которая просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и <math>g</math> будет занумерована, а следовательно и запущена. После остановки <math>g</math> и проверки правильности <math>y</math> программа <math>f</math> вернет его.
 
−
#Как выше уже оговаривалось, если программа <math>g(x)</math> правильно находит сертификат и завершается за <math>k</math> шагов, то программа <math>f</math> завершится не более, чем за <math>2^i \cdot (k + poly(|x + y|))</math> шагов. Заметим, что <math>2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))</math>, так как <math>y</math> — сертификат для <math>x</math> и потому <math>|y| \le poly(|x|)</math>.
 
−
 
 
−
Теорема доказана.
 

Текущая версия на 19:06, 4 сентября 2022

Теорема (Левин):
Для любого языка [math]L \in \Sigma_1[/math] и соответствующего ему (из определения [math]\Sigma_1[/math]) отношения [math]R[/math] существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа [math]p[/math], сопоставляющая словам из [math]L[/math] их сертификаты, то есть:
  1. [math]x \in L \Leftrightarrow R(x, p(x)) = 1[/math];
  2. для любой другой программы [math]q[/math], для которой верно [math]x \in L \Leftrightarrow R(x, q(x)) = 1[/math], найдутся такие константа [math]c[/math] и полином [math]r[/math], что для любого [math]x[/math] выполняется: [math]T(p, x) \le c \cdot T(q, x) + r(|x|)[/math].
Доказательство:
[math]\triangleright[/math]

Построим «оптимальную» программу [math]p(x)[/math].

Пронумеруем все программы [math]\lbrace p_i \rbrace_{i=1}^\infty[/math]. Подадим им на вход слово [math]x[/math] и будем исполнять по одной инструкции в следующем порядке: на шаге с номером [math]j[/math] запустим программу [math]p_k[/math], где [math]k[/math] таково, что [math]j[/math] делится на [math]2^{k-1}[/math] и не делится на [math]2^{k}[/math]. Таким образом, программа [math]p_k[/math] будет исполняться на каждом [math]2^k[/math]-м шаге начиная с [math]2^{k-1}[/math]-го. Следовательно, если [math]p_k[/math] завершит работу за [math]T(p_k, x)[/math] инструкций, то к этому времени нами будет сделано [math]2^{k-1} + (T(P_k, x) - 1) \cdot 2^k[/math] шагов.

Как только [math]p_k[/math], выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова [math]x[/math], используя вывод [math]p_k[/math] в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу, ничего не делая на тех шагах, когда должна была исполняться [math]p_k[/math].

Таким образом, если некоторая программа [math]q = p_m[/math] генерирует верные сертификаты, то наша программа [math]p[/math] завершит работу не более, чем за [math]2^{m-1} + (T(p_m,x) + T(R, \langle x,p_m(x) \rangle) - 1) \cdot 2^m[/math] шагов. [math]R \in P[/math] и [math]|y| \le poly(|x|)[/math] из определения [math]\Sigma_1[/math], значит это равно [math]2^{m-1} + (T(p_m,x) + poly(|x|)) \cdot 2^m = 2^m \cdot T(q,x) + poly(|x|)[/math].
[math]\triangleleft[/math]

См. также

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Теорема_Левина&oldid=84445»