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

Формулировка

Теорема Левина об оптимальной 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 (T(g, x) + poly(|x|))[/math]