Викиконспекты - Вклад участника [ru]

Теорема Бейкера — Гилла — Соловэя

2012-04-17T22:28:25Z

217.118.78.103:

{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>
| proof =
===Существование оракула <tex>A</tex>===
Покажем существование такого оракула <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>-полным языком]].
*<tex> \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} </tex>
* <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{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} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
===Существование оракула <tex>B</tex>===
Покажем существование такого оракула <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 2^n</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.
* 0-й шаг: <tex>B \leftarrow \emptyset </tex>
* <tex>i</tex>-й шаг. Будем считать шаги с 0-го по <tex>(i-1)</tex>-й сделаны. Тогда в <tex>B</tex> на данном этапе содержится конечное число слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^n</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, происходит следующее:
** Если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется.
** Если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^n</tex> шагов и вернуть какое-либо значение.
* Если <tex>M_i</tex> приняла слово, то будем считать, что в <tex>B</tex> не содержится слов вида <tex>\{0,1\}^n</tex>}.
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Тогда <tex>x \in B</tex>.

Если <tex>M_i</tex> допускает слово <tex>1^n</tex>, то в <tex>B</tex> нет слова <tex>1^n</tex>.
Если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>. Противоречие.
Следовательно, <tex>M_i</tex> не может решить язык <tex>U_B</tex> за время меньшее <tex>2^n</tex>.
}}

Теорема Бейкера — Гилла — Соловэя

2012-04-17T22:00:23Z

217.118.78.103:

{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>
| proof =
* Покажем существование такого оракула <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>-полным языком]].
**<tex> \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} </tex>
** <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{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} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
* Покажем существование такого оракула <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 2^n</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.
** 0-й шаг: <tex>B \leftarrow \emptyset </tex>
** <tex>i</tex>-й шаг. Будем считать шаги с 0-го по <tex>(i-1)</tex>-й сделаны. Тогда в <tex>B</tex> на данном этапе содержится конечное число слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^n</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, происходит следующее:
*** Если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется.
*** Если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^n</tex> шагов и вернуть какое-либо значение.
*** Если <tex>M_i</tex> приняла слово, то будем считать, что в <tex>B</tex> не содержится слов вида <tex>\{0,1\}^n</tex>}.
*** Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Тогда <tex>x \in B</tex>.

Если <tex>M_i</tex> допускает слово <tex>1^n</tex>, то в <tex>B</tex> нет слова <tex>1^n</tex>.
Если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>. Противоречие.
Следовательно, <tex>M_i</tex> не может решить язык <tex>U_B</tex> за время меньшее <tex>2^n</tex>.
}}

Теорема Бейкера — Гилла — Соловэя

2012-04-17T21:15:12Z

217.118.78.103:

{{ Теорема
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>
| proof =
* Покажем существование такого оракула <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>-полным языком]].
**<tex> \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} </tex>
** <tex>T(p,x) \ge S(p, x)</tex>, для любых <tex>p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{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} \-- \mathrm{PS}</tex>-полная <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
* {Покажем существование такого оракула <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 2^n</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.
** 0-й шаг: <tex>B \leftarrow \emptyset </tex>
** <tex>i</tex>-й шаг. Будем считать шаги с 0-го по <tex>(i-1)</tex>-й сделаны. Тогда в <tex>B</tex> на данном этапе содержится конечное число слов. Пусть самое длинное из них состоит из <tex>(n-1)</tex>-го символа. Запустим машину <tex>M_i</tex> на входе <tex>1^n</tex> на <tex>2^n</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, происходит следующее:
*** Если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется.
*** Если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^n</tex> шагов и вернуть какое-либо значение.
*** Если <tex>M_i</tex>, то будем считать, что в <tex>B</tex> не содержится слов вида <tex>\{0,1\}^n</tex>}
}}