Изменения

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

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

513 байт убрано, 23:45, 15 мая 2012
Теорема
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow 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>T(M_i</tex> не распознает язык <tex>U_B</tex> за время не большее, x) \ge чем <tex>2^{|x|n-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>.
* 0-я стадия: <tex>B \leftarrow \emptyset </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 \not\in B</tex>.
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>T(M_i, x) \ge </tex> не распознает <tex>U_B</tex> за время <tex>2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^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>), а всего слов длины n <tex>2^n</tex>.
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.
Рассмотрим построенное по описанному выше алгоритму множество <tex>B</tex>. ПредположимИз построения получаем, что никакая машина не может распознать <tex>M_iU_B</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, на слове <tex>1^n</tex>, где <tex>n</tex> определено для каждого <tex>i</tex> в алгоритме, описанном выше. Тогда *если <tex>M_i</tex> допускает слово <tex>1^n</tex>Следовательно, то в <tex>B</tex> нет слова <tex>1^n</tex>;*если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = nU_B \not\in \mathrm{P_B}</tex>.
Следовательно, никакая машина <tex>M_i</tex> не может решить язык <tex>U_B</tex> за время меньшее <tex>2^{n-1}</tex>.
}}
Анонимный участник

Навигация