Теорема Левина

По одному из определений [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], такая, что:

1. [math]\forall x \in L[/math] выполнено [math]R(x, f(x)) = 1[/math];
2. [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].