Теорема Бейкера — Гилла — Соловэя — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 35 промежуточных версий 15 участников)
Строка 1: Строка 1:
  
 +
==Теорема==
 
{{ Теорема
 
{{ Теорема
 
| statement = Существуют такие оракулы <tex>A</tex> и <tex>B</tex>, что <tex>\mathrm{P^A} = \mathrm{NP^A} </tex> и <tex>\mathrm{P^B} \ne \mathrm{NP^B} </tex>.
 
| 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 =  
 
| proof =  
'''Существование оракула <tex>A</tex>.'''
+
'''Существование оракула <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>-полным языком]].
+
Рассмотрим [[PS-полнота языка верных булевых формул с кванторами (TQBF) | PS-полный язык <tex>\mathrm{TQBF}</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>.
+
<tex>
* По [[ Класс PS. Теорема Сэвича. Совпадение классов NPS и PS | теореме Сэвича]] <tex> \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} </tex>.
+
\mathrm{P^{TQBF}}   \overset{(1)}{\subseteq}
* <tex> \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} </tex>.
+
\mathrm{NP^{TQBF}}  \overset{(2)}{\subseteq}
* <tex> \mathrm{TQBF} \-- \mathrm{PS}</tex>-полный <tex>\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}</tex>.
+
\mathrm{NPS^{TQBF}} \overset{(3)}{=}
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>.
+
\mathrm{PS^{TQBF}}  \overset{(4)}{=}
 +
\mathrm{PS}        \overset{(5)}{\subseteq}
 +
\mathrm{P^{TQBF}}
 +
\Rightarrow
 +
</tex><br/>
 +
<tex>\Rightarrow \mathrm{P^{TQBF}} = \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>.
 +
# По [[ Класс 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{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} </tex>.
 +
 
 +
Следовательно, <tex>\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}</tex>
  
 
----
 
----
  
'''Существование оракула <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> выполнено <tex>U_B \in \mathrm{NP}^B</tex> (сертификатом будет слово нужной длины из <tex>B</tex>). Построим такое множество <tex>B</tex>, что <tex>U_B \not\in \mathrm{P}^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>P_i</tex>. Множество <tex>B</tex> будем строить итеративно, на очередной итерации номер <tex>i</tex> делая так, что программа <tex>P_i</tex> не распознает множество <tex>U_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-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^B}</tex>. Начнем поэтапно строить множество <tex>B</tex>.
+
В начале каждой итерации определимся с тем, с какой длиной слова <tex>n_i</tex> мы будем работать. Для <tex>n_i</tex> должны быть выполнены три условия:
* 0-й шаг: <tex>B \leftarrow \emptyset </tex>
+
* <tex>2^{n_i} > T(P_i, (1)^{n_i})</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-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</tex>:
+
* <tex>n_i > n_{i-1}</tex> (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)
** если принадлежность <tex>x</tex> множеству <tex>B</tex> была определена на предыдущем шаге, то она сохраняется;
+
* <tex>n_i > \max\limits_{s \in B} |s|</tex>, где <tex>B</tex> {{---}} текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве <tex>B</tex> всегда конечное число элементов). Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, что в множестве <tex>B</tex> их нет.
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in B</tex>.
 
Но <tex>M_i</tex> могла остановится раньше, чем за <tex>2^{n-1}</tex> шагов и вернуть какое-либо значение. Но мы строим <tex>B</tex> с условием <tex>T(M_i, x) \ge 2^{n-1}</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>2^n-1</tex> запросов к оракулу, а всего слов длины n <tex>2^n</tex>.
 
  
Предположим, что <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, тогда
+
Затем запустим программу <tex>P_i</tex> на слове <tex>(1)^n</tex>. Каждый раз, когда она будет обращаться к оракулу для множества <tex>B</tex>, будем делать следующее:
*если <tex>M_i</tex> допускает слово <tex>1^n</tex>, то в <tex>B</tex> нет слова <tex>1^n</tex>;
+
* если запрошенное слово ранее было добавлено в множество <tex>B</tex>, отвечаем <tex>ACCEPT</tex>
*если <tex>M_i</tex> отклоняет слово <tex>1^n</tex>, то в <tex>B</tex> содержится слово <tex>x</tex>, причем <tex>|x| = n</tex>.
+
* в противном случае отвечаем <tex>REJECT</tex>
Противоречие.
+
 
Следовательно, <tex>M_i</tex> не может решить язык <tex>U_B</tex> за время меньшее <tex>2^{n-1}</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>, то оно не должно «релятивизоваться».
 +
}}
 +
 +
Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение <tex>\mathrm{P}</tex> и <tex>\mathrm{NP}</tex> не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.
 +
 +
[[Категория: Теория сложности]]

Текущая версия на 19:35, 4 сентября 2022

Теорема

Теорема:
Существуют такие оракулы [math]A[/math] и [math]B[/math], что [math]\mathrm{P^A} = \mathrm{NP^A} [/math] и [math]\mathrm{P^B} \ne \mathrm{NP^B} [/math].
Доказательство:
[math]\triangleright[/math]

Существование оракула [math]A[/math]

Рассмотрим PS-полный язык [math]\mathrm{TQBF}[/math].

[math] \mathrm{P^{TQBF}} \overset{(1)}{\subseteq} \mathrm{NP^{TQBF}} \overset{(2)}{\subseteq} \mathrm{NPS^{TQBF}} \overset{(3)}{=} \mathrm{PS^{TQBF}} \overset{(4)}{=} \mathrm{PS} \overset{(5)}{\subseteq} \mathrm{P^{TQBF}} \Rightarrow [/math]
[math]\Rightarrow \mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}[/math].

  1. [math] \mathrm{P} \subseteq \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subseteq \mathrm{NP^{TQBF}} [/math].
  2. Так как [math]S(p,x) \le T(p, x)[/math], то [math] \mathrm{NP} \subseteq \mathrm{NPS} \Rightarrow \mathrm{NP^{TQBF}} \subseteq \mathrm{NPS^{TQBF}} [/math].
  3. По теореме Сэвича [math] \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} [/math].
  4. [math] \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} [/math].
  5. [math] \mathrm{TQBF} \in \mathrm{PSC} \Rightarrow \mathrm{PS} \subseteq \mathrm{P^{TQBF}} [/math].

Следовательно, [math]\mathrm{P^{TQBF}} = \mathrm{NP^{TQBF}}[/math]


Существование оракула [math]B[/math]

Пусть [math]B[/math] — произвольное множество, а [math]U_B = \{1^n \bigm| \exists x \in B : |x| = n\}[/math]. Ясно, что [math]\forall B[/math] выполнено [math]U_B \in \mathrm{NP}^B[/math] (сертификатом будет слово нужной длины из [math]B[/math]). Построим такое множество [math]B[/math], что [math]U_B \not\in \mathrm{P}^B[/math].

Пронумеруем полиномиальные программы, получим последовательность [math]P_i[/math]. Множество [math]B[/math] будем строить итеративно, на очередной итерации номер [math]i[/math] делая так, что программа [math]P_i[/math] не распознает множество [math]U_B[/math].

В начале каждой итерации определимся с тем, с какой длиной слова [math]n_i[/math] мы будем работать. Для [math]n_i[/math] должны быть выполнены три условия:

  • [math]2^{n_i} \gt T(P_i, (1)^{n_i})[/math] (это ограничение может быть достигнуто, так как мы исследуем только полиномиальные программы)
  • [math]n_i \gt n_{i-1}[/math] (слово должно быть длиннее, чем слово, с которым мы работали на предыдущем шаге)
  • [math]n_i \gt \max\limits_{s \in B} |s|[/math], где [math]B[/math] — текущая версия множества, которое мы строим (это ограничение может быть достигнуто, так как в множестве [math]B[/math] всегда конечное число элементов). Кроме этого, слово должно быть длиннее, чем все слова, про которые наш оракул раньше ответил, что в множестве [math]B[/math] их нет.

Затем запустим программу [math]P_i[/math] на слове [math](1)^n[/math]. Каждый раз, когда она будет обращаться к оракулу для множества [math]B[/math], будем делать следующее:

  • если запрошенное слово ранее было добавлено в множество [math]B[/math], отвечаем [math]ACCEPT[/math]
  • в противном случае отвечаем [math]REJECT[/math]

Если программа отработала и решила, что слово [math](1)^n[/math] принадлежит языку [math]U_B[/math], ничего делать не надо: ни одного слова длины [math]n[/math] в языке [math]B[/math] нет (из-за третьего требования к длине обрабатываемых слов), и никогда не появится (из-за второго требования к длине обрабатываемых слов).

В противном случае, необходимо найти такое слово длины [math]n[/math], о котором программа [math]P_i[/math] не спрашивала оракул (оно всегда существует из-за первого требования к длине обрабатываемых слов: программа просто не успела бы спросить обо всех словах длины [math]n[/math]), и добавить это слово в множество [math]B[/math]. После этого все слова длины [math]n[/math] автоматически добавятся в язык [math]U_B[/math], и программа [math]P_i[/math] не будет верно распознавать этот язык (она будет неверно работать на слове [math](1)^n[/math]).
[math]\triangleleft[/math]

Следствие

Утверждение:
Если существует решение вопроса равенства [math]\mathrm{P}[/math] и [math] \mathrm{NP}[/math], то оно не должно «релятивизоваться».

Для доказательства строгого включения классов часто используется метод диагонализации. Однако утверждения, полученные при помощи данной техники, могут быть «релятивизованы». То есть при «разрешении» машине Тьюринга доступа к оракулу некоторого языка доказанное соотношение классов сохраняется. Однако соотношение [math]\mathrm{P}[/math] и [math]\mathrm{NP}[/math] не должно «релятивизоваться» по теореме Бейкера-Гилла-Соловэя, следовательно, метод диагонализации не применим для решения этого вопроса.