Изменения

{{Теорема|author== Формулировка =Левин|statement='''Теорема Левина об оптимальной NP-программе''' утверждает, что для Для любого языка <mathtex>L \in NP\Sigma_1</mathtex> и функции соответствующего ему (из определения <mathtex>R\Sigma_1</mathtex> - ) отношения <mathtex>NPR</mathtex> отношения для существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа <mathtex>Lp</mathtex> существует функция , сопоставляющая словам из <mathtex>fL</mathtex>их сертификаты, такая, чтото есть:#<mathtex>\forall x \in L</math> выполнено <math>\Leftrightarrow R(x, fp(x)) = 1</mathtex>;#для любой другой программы <mathtex>\forall gq</mathtex> - программы, такой, что для которой верно <mathtex>\forall x \in L \Leftrightarrow R(x, gq(x)) = 1</mathtex>, найдутся такие константа <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>. Пронумеруем все программы <mathtex>\forall 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) \in L cdot 2^k</tex> шагов. Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, будем на соответствующих шагах запускать проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу, ничего не делая на тех шагах, когда должна была исполняться <tex>p_k</tex>. Таким образом, если некоторая программа <tex>q = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{m-1} + (T(p_m,x) + T(fR, \langle x, p_m(x) \rangle) - 1) \cdot 2^m</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le C poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>2^{m-1} + (T(gp_m, x) + poly(|x|)) \cdot 2^m = 2^m \cdot T(q,x) + poly(|x|)</mathtex>.}} == См. также ==*[[Класс P]]*[[Классы_NP_и_Σ₁]] [[Категория: Теория сложности]]