Теорема Бейкера — Гилла — Соловэя — различия между версиями
(→Теорема) |
|||
Строка 29: | Строка 29: | ||
'''Существование оракула <tex>B</tex>''' | '''Существование оракула <tex>B</tex>''' | ||
− | Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow U_B \in \mathrm{NP^B | + | Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \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> | + | Пронумеруем некоторым образом все машины Тьюринга, имеющие доступ к оракулу языка <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 \emptyset </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>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</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in 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> | + | Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием, что для выбранного <tex>x = 1^n</tex> выполнено: <tex>T(M_i,x) \ge 2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным: |
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^n</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>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>. | ||
Строка 43: | Строка 43: | ||
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов. | Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов. | ||
− | Из построения получаем, что для любой машины Тьюринга <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>. |
}} | }} |
Версия 11:38, 4 июня 2012
Теорема
Теорема: |
Существуют такие оракулы и , что и . |
Доказательство: |
Существование оракула Рассмотрим PS-полный язык .
Существование оракула Пусть — произвольное множество, а . Ясно, что (сертификатом будет слово нужной длины из ). Построим такое множество , что .Пронумеруем некоторым образом все машины Тьюринга, имеющие доступ к оракулу языка , и рассмотрим последовательность , в которой каждая машина Тьюринга встречается бесконечное число раз. Очевидно, это можно сделать в силу счетности множества машин Тьюринга. Построение множества разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем строить так, чтобы на -й стадии было выполнено: существует слово , что . Это утверждение сильнее, чем , так как растет быстрее любого полинома.
Но могла остановится раньше, чем за шагов и вернуть какое-либо значение. Так как строится с условием, что для выбранного выполнено: , то решение машины о принадлежности слова должно быть неверным:
Во множестве Из построения получаем, что для любой машины Тьюринга на каждой стадии содержится конечное число элементов, так как на каждой стадии в может быть добавлено не более чем слов. существует бесконечно много слов из , для которых не может принять верное решение о принадлежности слова за время, меньшее . Следовательно, . |
Следствия
Утверждение: |
Методом диагонализации нельзя доказать, что . |
Утверждение: |
Если существует решение вопроса равенства и , то оно не должно "релятивизоваться", поэтому стандартные техники, например, диагонализация не применима. |