36
правок
Изменения
м
Новая страница: «== Формулировка == '''Теорема Левина об оптимальной NP-программе''' утверждает, что для любого …»
== Формулировка ==
'''Теорема Левина об оптимальной 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 (T(g, x) + poly(|x|))</math>
'''Теорема Левина об оптимальной 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 (T(g, x) + poly(|x|))</math>
