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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
По одному из определений <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 poly(|x|)</math> и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то и существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
+
По одному из определений <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 poly(|x|)</math> и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то и существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
  
 
Встает вопрос о возможности построения "оптимальной" программы для заранее заданного NP языка L и NP-отношения для этого языка R, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.
 
Встает вопрос о возможности построения "оптимальной" программы для заранее заданного NP языка L и NP-отношения для этого языка R, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.
Строка 13: Строка 13:
 
Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для него.
 
Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для него.
  
Занумеруем все программы <math>g_1, g_2, ... , g_n, ...</math> - сначала по длине программы, а в случае равенства длин - лексикографически.
+
Занумеруем все программы <math>g_1, g_2, ... , g_n, ...</math> сначала по длине программы, а в случае равенства длин - лексикографически.
  
 
Будем запускать <math>g_i</math> каждый раз на один шаг и запоминать полученное состояние запущенной программы. Запускать будем в следующем порядке: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 и так далее. Заметим, что мы запускаем программу <math>g_i</math> каждый <math>2^i</math>-й раз, а потому, если программа <math>g_i(x)</math> завершается за <math>k</math> шагов, то <math>f</math> совершит не больше <math>2^i \cdot k</math> шагов до момента завершения <math>g_i</math> на входе <math>x</math> в программе <math>f</math>.  
 
Будем запускать <math>g_i</math> каждый раз на один шаг и запоминать полученное состояние запущенной программы. Запускать будем в следующем порядке: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 и так далее. Заметим, что мы запускаем программу <math>g_i</math> каждый <math>2^i</math>-й раз, а потому, если программа <math>g_i(x)</math> завершается за <math>k</math> шагов, то <math>f</math> совершит не больше <math>2^i \cdot k</math> шагов до момента завершения <math>g_i</math> на входе <math>x</math> в программе <math>f</math>.  
Строка 21: Строка 21:
 
Осталось доказать, что данная программа действительно удовлетворяет пунктам 1 и 2 теоремы Левина.
 
Осталось доказать, что данная программа действительно удовлетворяет пунктам 1 и 2 теоремы Левина.
 
#Так как программа f возвращает только те у, для которых R(x, y) = 1, то R(x, f(x)) = 0 получиться не может. Покажем, что и зависнуть на словах из языка <math>f</math> не может. Как выше уже упоминалось, если слово принадлежит языку <math>L</math>, то для него есть сертификат, а значит есть и программа <math>g</math>, которая просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и <math>g</math> будет занумерована, а следовательно и запущена. После остановки <math>g</math> и проверки правильности <math>y</math> программа <math>f</math> вернет его.
 
#Так как программа f возвращает только те у, для которых R(x, y) = 1, то R(x, f(x)) = 0 получиться не может. Покажем, что и зависнуть на словах из языка <math>f</math> не может. Как выше уже упоминалось, если слово принадлежит языку <math>L</math>, то для него есть сертификат, а значит есть и программа <math>g</math>, которая просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и <math>g</math> будет занумерована, а следовательно и запущена. После остановки <math>g</math> и проверки правильности <math>y</math> программа <math>f</math> вернет его.
#Как выше уже оговаривалось, если программа <math>g(x)</math> правильно находит сертификат и завершится за <math>k</math> шагов, то программа <math>f</math> завершится не более, чем за <math>2^i \cdot (k + poly(|x + y|))</math> шагов. Заметим, что <math>2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))</math>, так как <math>y</math> - сертификат для <math>x</math> и потому <math>|y| \le poly(|x|)</math>.
+
#Как выше уже оговаривалось, если программа <math>g(x)</math> правильно находит сертификат и завершится за <math>k</math> шагов, то программа <math>f</math> завершится не более, чем за <math>2^i \cdot (k + poly(|x + y|))</math> шагов. Заметим, что <math>2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))</math>, так как <math>y</math> сертификат для <math>x</math> и потому <math>|y| \le poly(|x|)</math>.
  
 
Теорема доказана.
 
Теорема доказана.

Версия 11:56, 14 марта 2010

По одному из определений [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 poly(|x|)[/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) не зависит от слова х, т.е. константа от х.

Доказательство

Для доказательства теоремы будем строить оптимальную NP программу f для некоторого NP языка L и NP отношения R(x, y) для него.

Занумеруем все программы [math]g_1, g_2, ... , g_n, ...[/math] сначала по длине программы, а в случае равенства длин - лексикографически.

Будем запускать [math]g_i[/math] каждый раз на один шаг и запоминать полученное состояние запущенной программы. Запускать будем в следующем порядке: 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5 и так далее. Заметим, что мы запускаем программу [math]g_i[/math] каждый [math]2^i[/math]-й раз, а потому, если программа [math]g_i(x)[/math] завершается за [math]k[/math] шагов, то [math]f[/math] совершит не больше [math]2^i \cdot k[/math] шагов до момента завершения [math]g_i[/math] на входе [math]x[/math] в программе [math]f[/math].

После того, как программа [math]g_i[/math] остановилась, на её месте будем запускать программу [math]R(x, y)[/math], где [math]y[/math] - значение, которое вернула [math]g_i(x)[/math]. Причем f совершит не больше [math]2^i \cdot poly(|x + y|)[/math] шагов до завершения программы [math]R(x, y)[/math], так как [math]R \in \tilde{P}[/math] и она запускается каждый [math]2^i[/math]-й раз. Если [math]R(x, y)[/math] вернула [math]true[/math], то возвратим [math]y[/math], т.к. [math]y[/math] - нужный сертификат для [math]x[/math], а если [math]false[/math], то ничего на этом месте больше запускать не будем.

Осталось доказать, что данная программа действительно удовлетворяет пунктам 1 и 2 теоремы Левина.

  1. Так как программа f возвращает только те у, для которых R(x, y) = 1, то R(x, f(x)) = 0 получиться не может. Покажем, что и зависнуть на словах из языка [math]f[/math] не может. Как выше уже упоминалось, если слово принадлежит языку [math]L[/math], то для него есть сертификат, а значит есть и программа [math]g[/math], которая просто этот сертификат возвращает. Так как все программы рано или поздно будут занумерованы, то и [math]g[/math] будет занумерована, а следовательно и запущена. После остановки [math]g[/math] и проверки правильности [math]y[/math] программа [math]f[/math] вернет его.
  2. Как выше уже оговаривалось, если программа [math]g(x)[/math] правильно находит сертификат и завершится за [math]k[/math] шагов, то программа [math]f[/math] завершится не более, чем за [math]2^i \cdot (k + poly(|x + y|))[/math] шагов. Заметим, что [math]2^i \cdot (k + poly(|x + y|))=2^i \cdot (k + poly(|x|))[/math], так как [math]y[/math] — сертификат для [math]x[/math] и потому [math]|y| \le poly(|x|)[/math].

Теорема доказана.