1632
правки
Изменения
м
rollbackEdits.php mass rollback
* <tex>2^{n_i} > T(P_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>P_i</tex> на слове <tex>(1)^n</tex>. Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex>, будем делать следующее:
