36
правок
Изменения
Нет описания правки
'''Теорема Левина об оптимальной NP программе''' утверждает, что для любого языка <math>L \in NP</math> и функции <math>R</math> (<math>NP</math>-отношения для <math>L</math>) существует программа <math>f</math>, такая, что:
#<math>\forall x \in L</math> выполнено <math>R(x, f(x)) = 1</math>;
#<math>\forall g</math> - — программы, такой, что <math>\forall x \in L: R(x, g(x)) = 1</math> выполнено <math>\forall x \in L: T(f, x) \le C(g) \cdot (T(g, x) + poly(|x|))</math>, где T(f, x) - — время работы программы f на входе x.
Заметим, что функция C(g) не зависит от слова х, т.е. константа от х.
Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для него.
Занумеруем все программы <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 теоремы Левина.
