Изменения
Нет описания правки
'''Существование оракула <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> (сертификатом будет слово нужной длины из <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>M_i</tex> не разрешает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-1}</tex>. Очевидно, что это Это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>, так как <tex>2^n</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>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.
Из построения получаем, что никакая машина не может разрешить для любой машины Тьюринга <tex>M_i</tex> существует бесконечно много слов из <tex>U_B</tex> , которые <tex>M_i</tex> не может разрешить за время меньшее <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P_B}</tex>.
}}
