171
правка
Изменения
м
Нет описания правки
Пронумеруем некоторым образом все машины Тьюринга, работающие за полиномиальное время и имеющие доступ к оракулу языка <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 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>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>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> слов.
{{ Утверждение
| statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно "релятивизоваться"«релятивизоваться».
}}
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения , полученные при помощи данной техники , могут быть "релятивизованы"«релятивизованы». То есть при "разрешении" «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно "релятивизоваться" «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.
[[Категория: Теория сложности]]
