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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 19: Строка 19:
 
Покажем существование такого оракула <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>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-1}</tex>. Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P_B}</tex>. Начнем поэтапно строить множество <tex>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>.
 
* 0-й шаг: <tex>B \leftarrow \emptyset </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-1}</tex> шагов. Когда <tex>M_i</tex> требуется ответ оракула языка <tex>B</tex> о слове <tex>x</tex>, будем определять принадлежность этого слова к <tex>B</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>:

Версия 12:38, 29 апреля 2012

Теорема:
Существуют такие оракулы [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].

Покажем существование такого оракула [math]A[/math], что [math]\mathrm{P^A} = \mathrm{NP^A} [/math]. Рассмотрим язык [math] \mathrm{TQBF} = \{ \Phi | \Phi \--[/math] булева формула с кванторами [math], \Phi = 1\}[/math]. [math] \mathrm{TQBF} [/math] является [math]PS[/math]-полным языком.

  • [math] \mathrm{P} \subset \mathrm{NP} \Rightarrow \mathrm{P^{TQBF}} \subset \mathrm{NP^{TQBF}} [/math].
  • [math]T(p,x) \ge S(p, x)[/math], для любых [math]p, x \Rightarrow \mathrm{NP^{TQBF}} \subset \mathrm{NPS^{TQBF}}[/math].
  • По теореме Сэвича [math] \mathrm{NPS^{TQBF}} = \mathrm{PS^{TQBF}} [/math].
  • [math] \mathrm{TQBF} \in \mathrm{PS} \Rightarrow \mathrm{PS^{TQBF}} = \mathrm{PS} [/math].
  • [math] \mathrm{TQBF} \-- \mathrm{PS}[/math]-полный [math]\Rightarrow \mathrm{PS} \in \mathrm{P^{TQBF}}[/math].

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


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

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

Рассмотрим последовательность машин Тьюринга [math]M_i[/math], имеющих доступ к оракулу языка [math]B[/math]. Построение множество [math]B[/math] разделим на счетное число шагов. Будем строить [math]B[/math] так, чтобы на [math]i[/math]-м шаге было выполнено: [math]T(M_i, x) \ge 2^{n-1}[/math]. Очевидно, что это утверждение сильнее, чем [math]U_B \not\in \mathrm{P^B}[/math]. Начнем поэтапно строить множество [math]B[/math].

  • 0-й шаг: [math]B \leftarrow \emptyset [/math]
  • [math]i[/math]-й шаг. Будем считать шаги с 0-го по [math](i-1)[/math]-й сделаны. Тогда [math]B[/math] на данном этапе — конечное множество слов. Пусть самое длинное из них состоит из [math](n-1)[/math]-го символа. Запустим машину [math]M_i[/math] на входе [math]1^n[/math] на [math]2^{n-1}[/math] шагов. Когда [math]M_i[/math] требуется ответ оракула языка [math]B[/math] о слове [math]x[/math], будем определять принадлежность этого слова к [math]B[/math]:
    • если принадлежность [math]x[/math] множеству [math]B[/math] была определена на предыдущем шаге, то она сохраняется;
    • если принадлежность [math]x[/math] множеству [math]B[/math] не установлена ранее, то далее считаем, что [math]x \not\in B[/math].

Но [math]M_i[/math] могла остановится раньше, чем за [math]2^{n-1}[/math] шагов и вернуть какое-либо значение. Но мы строим [math]B[/math] с условием [math]T(M_i, x) \ge 2^{n-1}[/math], поэтому решение машины должно быть неверным:

  • если [math]M_i[/math] приняла слово, то будем считать, что выбросим из [math]B[/math] все слова вида [math]\{0,1\}^n[/math];
  • Если [math]M_i[/math] отклонила слово, то выберем слово [math]x[/math] длины [math]n[/math], принадлежность которого [math]B[/math] еще не определено. Тогда [math]x \in B[/math]. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем [math]2^n-1[/math] запросов к оракулу, а всего слов длины n [math]2^n[/math].

Предположим, что [math]M_i[/math] отработала менее, чем за время [math]2^{n-1}[/math], тогда

  • если [math]M_i[/math] допускает слово [math]1^n[/math], то в [math]B[/math] нет слова [math]1^n[/math];
  • если [math]M_i[/math] отклоняет слово [math]1^n[/math], то в [math]B[/math] содержится слово [math]x[/math], причем [math]|x| = n[/math].

Противоречие.

Следовательно, [math]M_i[/math] не может решить язык [math]U_B[/math] за время меньшее [math]2^{n-1}[/math].
[math]\triangleleft[/math]