Теорема Бейкера — Гилла — Соловэя — различия между версиями
(→Теорема) |
м (rollbackEdits.php mass rollback) |
||
(не показано 13 промежуточных версий 7 участников) | |||
Строка 20: | Строка 20: | ||
# <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>. | # <tex> \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} </tex>. | ||
− | # Так как <tex>S(p,x) \le T(p, x)</tex>, то<tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>. | + | # Так как <tex>S(p,x) \le T(p, x)</tex>, то <tex> \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} </tex>. |
# По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>. | # По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>. | ||
# <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>. | # <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>. | ||
# <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>. | # <tex> \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>. | ||
+ | |||
+ | Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex> | ||
---- | ---- | ||
Строка 29: | Строка 31: | ||
'''Существование оракула <tex>B</tex>''' | '''Существование оракула <tex>B</tex>''' | ||
− | Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n \bigm| \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B | + | Пусть <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>P_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, что программа <tex>P_i</tex> не распознает множество <tex>U_B</tex>. |
− | |||
− | |||
− | |||
− | |||
− | + | В начале каждой итерации определимся с тем, с какой длиной слова <tex>n_i</tex> мы будем работать. Для <tex>n_i</tex> должны быть выполнены три условия: | |
− | * | + | * <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>, будем делать следующее: | |
+ | * если запрошенное слово ранее было добавлено в множество <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>P_i</tex> не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины <tex>n</tex>), и добавить это слово в множество <tex>B</tex>. После этого все слова длины <tex>n</tex> автоматически добавятся в язык <tex>U_B</tex>, и программа <tex>P_i</tex> не будет верно распознавать этот язык (она будет неверно работать на слове <tex>(1)^n</tex>). | ||
}} | }} | ||
− | == | + | ==Следствие== |
{{ Утверждение | {{ Утверждение | ||
− | | statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно | + | | statement = Если существует решение вопроса равенства <tex>\mathrm{P}</tex> и <tex> \mathrm{NP}</tex>, то оно не должно «релятивизоваться». |
}} | }} | ||
+ | |||
+ | Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса. | ||
[[Категория: Теория сложности]] | [[Категория: Теория сложности]] |
Текущая версия на 19:35, 4 сентября 2022
Теорема
Теорема: |
Существуют такие оракулы и , что и . |
Доказательство: |
Существование оракула Рассмотрим PS-полный язык .
Следовательно, Существование оракула Пусть — произвольное множество, а . Ясно, что выполнено (сертификатом будет слово нужной длины из ). Построим такое множество , что .Пронумеруем полиномиальные программы, получим последовательность . Множество будем строить итеративно, на очередной итерации номер делая так, что программа не распознает множество .В начале каждой итерации определимся с тем, с какой длиной слова мы будем работать. Для должны быть выполнены три условия:
Затем запустим программу на слове . Каждый раз, когда она будет обращаться к оракулу для множества , будем делать следующее:
Если программа отработала и решила, что слово В противном случае, необходимо найти такое слово длины принадлежит языку , ничего делать не надо: ни одного слова длины в языке нет (из-за третьего требования к длине обрабатываемых слов), и никогда не появится (из-за второго требования к длине обрабатываемых слов). , о котором программа не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины ), и добавить это слово в множество . После этого все слова длины автоматически добавятся в язык , и программа не будет верно распознавать этот язык (она будет неверно работать на слове ). |
Следствие
Утверждение: |
Если существует решение вопроса равенства и , то оно не должно «релятивизоваться». |
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение
и не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.