Изменения

Перейти к: навигация, поиск

Теорема Бейкера — Гилла — Соловэя

3103 байта убрано, 19:35, 5 июня 2013
Теорема
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B</tex> выполнено <tex>U_B \in \mathrm{NP}^B</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P}^B</tex>.
Пронумеруем некоторым образом все машины Тьюрингаполиномиальные программы, работающие за полиномиальное время и имеющие доступ к оракулу языка <tex>B</tex>, и рассмотрим получим последовательность <tex>M_i</tex>, в которой каждая машина Тьюринга встречается бесконечное число раз. Очевидно, это можно сделать в силу счетности множества машин Тьюринга. Построение множества Множество <tex>B</tex> разделим на счетное число стадий. Будем будем строить <tex>B</tex> такитеративно, чтобы на очередной итерации номер <tex>i</tex>-й стадии было выполнено: существует слово <tex>x</tex>делая так, что программа <tex>T(M_i, x) \ge 2^{n-1}</tex>. Это утверждение сильнее, чем не распознает множество <tex>U_B \not\in \mathrm{P}^B</tex>, так как <tex>2^n</tex> растет быстрее любого полинома.* 0-я стадия: <tex>B \leftarrow \varnothing </tex>.* <tex>i</tex>-я стадия. Стадии с 0-й по <tex>(i-1)</tex>-ю пройдены, <tex>B</tex> — конечное множество слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^{n-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex> следующим образом:** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на одной из предыдущих стадий, то она сохраняется;** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <tex>M_i</tex> могла остановиться раньшеВ начале каждой итерации определимся с тем, чем за с какой длиной слова <tex>2^{n-1}</tex> шагов, и вернуть какое-либо значениемы будем работать. Так как Для <tex>Bn</tex> строится с условием, что для выбранного должны быть выполнены два условия:* <tex>x = 12^n</tex> выполнено: <tex>T(M_i,x(1) \ge 2^{n-1}</tex>(это ограничение может быть достигнуто, то решение машины о принадлежности слова должно быть неверным:так как мы исследуем только полиномиальные программы)* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <texn >\max_{0,1s \in B} |s|}^n</tex>;* Если <tex>M_i</tex> отклонила слово(это ограничение может быть достигнуто, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определена. Добавим <tex>x</tex> так как в множестве <tex>B</tex>. Такое слово всегда найдется, так как на предыдущих шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>конечное количество элементов), а всего слов длины <tex>n</tex> <tex>2^n</tex>.
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.
Из построения получаем, что для любой машины Тьюринга <tex>M</tex> существует бесконечно много слов из <tex>U_B</tex>, для которых <tex>M</tex> не может принять верное решение о принадлежности слова <tex>U_B</tex> за время, меньшее <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P}^B</tex>.
}}
Анонимный участник

Навигация