36
правок
Изменения
Нет описания правки
По одному из определений <math>NP</math> языка, язык <math>L</math> принадлежит <math>NP</math>, если существует функция <math>R(x, y) \in \tilde{P}</math> - <math>NP</math>-отношение для языка <math>L</math> (<math>NP</math>-relation), такая, что: <math>x \in L \Leftrightarrow \exists y</math> - сертификат для <math>x</math>, такой, что: <math>|y| \le p(|x|)</math> (<math>p</math> - некоторый полином) и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то и существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
Встает вопрос о возможности построения "оптимальной" программы для заранее заданного NP языка L и NP-отношения для этого языка R, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.
== Формулировка ==
'''Теорема Левина об оптимальной 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) не зависит от слова х, т.е. константа от х. == Доказательство ==Занумеруем все программы <math>g_1, g_2, ... , g_n, ...</math>.
