Изменения

По одному из определений <mathtex>NP</mathtex> языка, язык <mathtex>L</mathtex> принадлежит <mathtex>NP</mathtex>, если существует такая функция <mathtex>R(x, y) \in \tilde{P}</mathtex> — <mathtex>NP</mathtex>-отношение для языка <mathtex>L</mathtex> (<mathtex>NP</mathtex>-relation), что: <mathtex>x \in L \Leftrightarrow \exists y</mathtex> — такой сертификат для <mathtex>x</mathtex>, что: <mathtex>|y| \le poly(|x|)</mathtex> и <mathtex>R(x, y) = 1</mathtex>. Таким образом, для проверки принадлежности некоторого слова <tex>NP </tex> языку <tex>L </tex> с <tex>NP</tex>-отношением <tex>R </tex> необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то существует программа <tex>g(x)</tex>, которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет, и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.

Встает вопрос о возможности построения «оптимальной» программы для заранее заданного <tex>NP </tex> языка <tex>L </tex> и <tex>NP</tex>-отношения для этого языка <tex>R</tex>, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.

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

Заметим, что функция <tex>C(g) </tex> не зависит от слова х<tex>x</tex>, т.е. константа от х<tex>x</tex>.

Для доказательства теоремы будем строить оптимальную <tex>NP </tex> программу <tex>f </tex> для некоторого <tex>NP </tex> языка <tex>L </tex> и <tex>NP </tex> отношения <tex>R(x, y) </tex> для него.

Занумеруем все программы <mathtex>g_1, g_2, ... , g_n, ...</mathtex> сначала по длине программы, а в случае равенства длин — лексикографически.

Будем запускать <mathtex>g_i</mathtex> каждый раз на один шаг и запоминать полученное состояние запущенной программы. Запускать будем в следующем порядке: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 и так далее. Заметим, что мы запускаем программу <mathtex>g_i</mathtex> каждый <mathtex>2^i</mathtex>-й раз, а потому, если программа <mathtex>g_i(x)</mathtex> завершается за <mathtex>k</mathtex> шагов, то <mathtex>f</mathtex> совершит не больше <mathtex>2^i \cdot k</mathtex> шагов до момента завершения <mathtex>g_i</mathtex> на входе <mathtex>x</mathtex> в программе <mathtex>f</mathtex>.

После того, как программа <mathtex>g_i</mathtex> остановилась, на её месте будем запускать программу <mathtex>R(x, y)</mathtex>, где <mathtex>y</mathtex> - значение, которое вернула <mathtex>g_i(x)</mathtex>. Причем <tex>f </tex> совершит не больше <mathtex>2^i \cdot poly(|x + y|)</mathtex> шагов до завершения программы <mathtex>R(x, y)</mathtex>, так как <mathtex>R \in \tilde{P}</mathtex> и она запускается каждый <mathtex>2^i</mathtex>-й раз. Если <mathtex>R(x, y)</mathtex> вернула <mathtex>true</mathtex>, то возвратим <mathtex>y</mathtex>, так как <mathtex>y</mathtex> — нужный сертификат для <mathtex>x</mathtex>, а если <mathtex>false</mathtex>, то ничего на этом месте больше запускать не будем.

#Так как программа <tex>f </tex> возвращает только те у<tex>y</tex>, для которых <tex>R(x, y) = 1</tex>, то <tex>R(x, f(x)) = 0 </tex> получиться не может. Покажем, что и зависнуть на словах из языка <mathtex>f</mathtex> не может. Как выше уже упоминалось, если слово принадлежит языку <mathtex>L</mathtex>, то для него есть сертификат, а значит есть и программа <mathtex>g</mathtex>, которая просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и <mathtex>g</mathtex> будет занумерована, а следовательно и запущена. После остановки <mathtex>g</mathtex> и проверки правильности <mathtex>y</mathtex> программа <mathtex>f</mathtex> вернет его.#Как выше уже оговаривалось, если программа <mathtex>g(x)</mathtex> правильно находит сертификат и завершается за <mathtex>k</mathtex> шагов, то программа <mathtex>f</mathtex> завершится не более, чем за <mathtex>2^i \cdot (k + poly(|x + y|))</mathtex> шагов. Заметим, что <mathtex>2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))</mathtex>, так как <mathtex>y</mathtex> — сертификат для <mathtex>x</mathtex> и потому <mathtex>|y| \le poly(|x|)</mathtex>.