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