Теорема Левина

Теорема (Левин):

Для любого языка [math]L \in \Sigma_1[/math] и соответствующего ему (из определения [math]\Sigma_1[/math]) отношения [math]R[/math] существует «оптимальная» (работающая «не сильно дольше», чем любая другая) программа [math]p[/math], сопоставляющая словам из [math]L[/math] их сертификаты, то есть: [math]x \in L \Leftrightarrow R(x, p(x)) = 1[/math]; для любой другой программы [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]

См. также

• Класс P
• Классы_NP_и_Σ₁