По одному {{Теорема|author=Левин|statement=Для любого языка <tex>L \in \Sigma_1</tex> и соответствующего ему (из определений определения <mathtex>NP\Sigma_1</tex>) отношения <tex>R</mathtex> языкасуществует «оптимальная» (работающая «не сильно дольше», язык чем любая другая) программа <mathtex>Lp</mathtex> принадлежит , сопоставляющая словам из <mathtex>NPL</mathtex>их сертификаты, если существует функция то есть:# <mathtex>x \in L \Leftrightarrow R(x, yp(x) \in \tilde{P}) = 1</mathtex> — ;# для любой другой программы <mathtex>NPq</mathtex>-отношение , для языка которой верно <mathtex>x \in L\Leftrightarrow R(x, q(x)) = 1</mathtex> (, найдутся такие константа <mathtex>NPc</mathtex>-relation), такая, что: и полином <mathtex>x \in L \Leftrightarrow \exists yr</mathtex> — сертификат , что для любого <mathtex>x</mathtex>, такой, чтовыполняется: <mathtex>|y| T(p, x) \le polyc \cdot T(q, x) + r(|x|)</mathtex> и .|proof=Построим «оптимальную» программу <mathtex>Rp(x, y) = 1</mathtex>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то и существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
Встает вопрос о возможности построения "оптимальной" Пронумеруем все программы для заранее заданного NP языка L <tex>\lbrace p_i \rbrace_{i=1}^\infty</tex>. Подадим им на вход слово <tex>x</tex> и NPбудем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^{k-отношения для этого языка R1}</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> шагов.
== Формулировка =='''Теорема Левина об оптимальной NP программе''' утверждает, что для любого языка Как только <mathtex>L \in NPp_k</math> и функции <math>R</math> (<math>NP</math>-отношения для <math>L</math>) существует программа <math>f</mathtex>, такаявыдав некоторое значение, завершит работу, что:#будем на соответствующих шагах запускать проверку сертификата слова <mathtex>\forall x \in L</math> выполнено <mathtex>R(x, f(x)) = 1</math>;#используя вывод <mathtex>\forall gp_k</mathtex> - программыв качестве сертификата. Если результат проверки положителен, такойискомый сертификат найден, что <math>\forall x \in L: R(xиначе — продолжим работу, ничего не делая на тех шагах, g(x)) = 1когда должна была исполняться </mathtex> выполнено <math>\forall x \in L: T(f, x) \le C(g) \cdot (T(g, x) + poly(|x|))p_k</mathtex>, где T(f, x) - время работы программы f на входе x.
ЗаметимТаким образом, что функция Cесли некоторая программа <tex>q = p_m</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>2^{m-1} + (gT(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>. Теорема доказана.Теория сложности]]
