http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=217.118.78.43&*
Викиконспекты - Вклад участника [ru]
2026-08-05T06:45:41Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%91%D0%B5%D0%B9%D0%BA%D0%B5%D1%80%D0%B0_%E2%80%94_%D0%93%D0%B8%D0%BB%D0%BB%D0%B0_%E2%80%94_%D0%A1%D0%BE%D0%BB%D0%BE%D0%B2%D1%8D%D1%8F&diff=20869
Теорема Бейкера — Гилла — Соловэя
2012-04-17T18:47:25Z
<p>217.118.78.43: </p>
<hr />
<div>{{ Теорема<br />
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex><br />
| proof = <br />
* Покажем существование такого оракула <tex>A</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex>. Рассмотрим язык <tex> \mathrm{TQBF} = \{ \Phi | \Phi \--</tex> булева формула с кванторами <tex>, \Phi = 1\}</tex>. [[PS-полнота языка верных булевых формул с кванторами (TQBF) | <tex> \mathrm{TQBF} </tex> является <tex>PS</tex>-полным языком]].<br />
**<tex> \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} </tex><br />
** <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{TQBF}}</tex><br />
** По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex><br />
** <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex><br />
** <tex> \mathrm{TQBF} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex> <br />
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex><br />
* Покажем существование такого оракула <tex>B</tex>, что <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>. Пусть <tex>B\--</tex> произвольное множество, а <tex>U_B = \{1^n | \exists x</tex>, что <tex>|x| = n\}</tex>. Ясно, что <tex>\forall B: U_B \in \mathrm{NP^B}</tex> (легко написать программу, проверяющую сертификат). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P^B}</tex>. Рассмотрим последовательность машин Тьюринга <tex>M_i</tex>, имеющих доступ к оракулу языка <tex>B</tex>. Построение множество <tex>B</tex> разделим на счетное число шагов. Будем строить <tex>B</tex> так, что на <tex>i-</tex>м шаге выполнено: <tex>T(M_i, x) \ge \frac{2^n}{10}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.<br />
** 0-й шаг: <tex>B \leftarrow \emptyset </tex><br />
** <tex>i</tex>-й шаг.<br />
}}</div>
217.118.78.43