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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема)
м
Строка 10: Строка 10:
 
Пронумеруем все программы <tex>p_i</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^k</tex> и не делится на <tex>2^{k+1}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>T(P_k, x) \cdot 2^k</tex> шагов.
 
Пронумеруем все программы <tex>p_i</tex>. Поместим их в различные потоки, подадим на вход слово <tex>x</tex> и будем исполнять по одной инструкции в следующем порядке: на шаге с номером <tex>j</tex> запустим программу <tex>p_k</tex>, где <tex>k</tex> таково, что <tex>j</tex> делится на <tex>2^k</tex> и не делится на <tex>2^{k+1}</tex>. Таким образом, программа <tex>p_k</tex> будет исполняться на каждом <tex>2^k</tex>-м шаге. Следовательно, если <tex>p_k</tex> завершит работу за <tex>T(p_k, x)</tex> инструкций, то к этому времени нами будет сделано <tex>T(P_k, x) \cdot 2^k</tex> шагов.
  
Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу запустим в том же потоке проверку сертификата слова <tex>x</tex>, использовав вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.
+
Как только <tex>p_k</tex>, выдав некоторое значение, завершит работу, запустим в том же потоке проверку сертификата слова <tex>x</tex>, используя вывод <tex>p_k</tex> в качестве сертификата. Если результат проверки положителен, искомый сертификат найден, иначе — продолжим работу больше ничего не запуская в этом потоке.
  
 
Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>(T(p_k,x) + T(R, \langle x,p_k(x) \rangle)) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>(T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.
 
Таким образом, если некоторая программа <tex>p_k</tex> генерирует верные сертификаты, то наша программа <tex>p</tex> завершит работу не более, чем за <tex>(T(p_k,x) + T(R, \langle x,p_k(x) \rangle)) \cdot 2^k</tex> шагов. <tex>R \in P</tex> и <tex>|y| \le poly(|x|)</tex> из определения <tex>\Sigma_1</tex>, значит это равно <tex>(T(p_k,x) + poly(|x|)) \cdot 2^k = 2^k \cdot T(p_k,x) + poly(|x|)</tex>.

Версия 21:56, 8 мая 2012

Теорема (Левин):
Для любого языка [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]\forall x \Rightarrow T(p, x) \le c \cdot T(q, x) + r(|x|)[/math].
Доказательство:
[math]\triangleright[/math]

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

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

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

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

См. также