Теорема Левина — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Новая страница: «== Формулировка == '''Теорема Левина об оптимальной NP-программе''' утверждает, что для любого …»)
(нет различий)

Версия 21:38, 9 марта 2010

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

Теорема Левина об оптимальной 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]