36
правок
Изменения
Нет описания правки
По одному из определений <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 ppoly(|x|)</math> (<math>p</math> - некоторый полином) и <math>R(x, y) = 1</math>. Таким образом, для проверки принадлежности некоторого слова NP языку L с NP-отношением R необходимо предъявить соответствующий сертификат. Так как для любого слова из языка существует подтверждающий сертификат, то и существует программа g(x), которая для слов из языка возвращает нужный сертификат. А для слов не из языка никаких гарантий на возвращаемое значение функции нет и потому она может либо вернуть неправильный сертификат, либо вообще зависнуть.
Встает вопрос о возможности построения "оптимальной" программы для заранее заданного NP языка L и NP-отношения для этого языка R, которая будет находить сертификат для слова. Оптимальность программы в данном случае означает, что время ее работы для слов из языка не сильно хуже, чем у любой другой программы, правильно находящей сертификат для слов из языка.
Осталось доказать, что данная программа действительно удовлетворяет пунктам 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> вернет его.
#Как выше уже оговаривалось, если программа <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 ppoly(|x|)</math>.
Теорема доказана.
