Изменения
Нет описания правки
'''Существование оракула <tex>B</tex>'''
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow </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> растет быстрее любого полинома.
