Изменения
→Теорема
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B</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>M_iP_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, что программа <tex>M_iP_i</tex> не распознает множество <tex>U_B</tex>.
В начале каждой итерации определимся с тем, с какой длиной слова <tex>n_i</tex> мы будем работать. Для <tex>n_i</tex> должны быть выполнены три условия:
* <tex>2^{n_i} > T(M_iP_i, (1)^{n_i})</tex> (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)
* <tex>n_i > n_{i-1}</tex> (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)
* <tex>n_i > \max\limits_{s \in B} |s|</tex>, где <tex>B</tex> {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>B</tex> всегда конечное число элементов). Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, что в множестве <tex>B</tex> их нет.
Затем запустим программу <tex>M_iP_i</tex> на слове <tex>(1)^n</tex>. Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex>, будем делать следующее:
* если запрошенное слово ранее было добавлено в множество <tex>B</tex>, отвечаем <tex>ACCEPT</tex>
* в противном случае отвечаем <tex>REJECT</tex>
Если программа отработала и решила, что слово <tex>(1)^n</tex> принадлежит языку <tex>U_B</tex>, ничего делать не надо: ни одного слова длины <tex>n</tex> в языке <tex>B</tex> нет (из-за третьего требования к длине обрабатываемых слов), и никогда не появится (из-за второго требования к длине обрабатываемых слов).
В противном случае, необходимо найти такое слово длины <tex>n</tex>, о котором программа <tex>M_iP_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>n</tex>), и добавить это слово в множество <tex>B</tex>. После этого все слова длины <tex>n</tex> автоматически добавятся в язык <tex>U_B</tex>, и программа <tex>M_iP_i</tex> не будет верно распознавать этот язык (она будет неверно работать на слове <tex>(1)^n</tex>).
}}
