36
правок
Изменения
Нет описания правки
== Доказательство ==
Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для L.
Занумеруем все программы <math>g_1, g_2, ... , g_n, ...</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>g_i</math> остановилась, на её месте будем запускать программу <math>R(x, y)</math>, где <math>y</math> - значение, которое вернула <math>g_i(x)</math>. Причем f совершит не больше <math>2^i \cdot poly(|x + y|) = 2^i \cdot poly(|x|)</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|))</math> шагов.
Теорема доказана.
