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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теорема: немного подправил, но всё плохо)
(Теорема)
Строка 30: Строка 30:
 
Пусть <tex>B</tex> — произвольное множество, а <tex>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow 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>U_B = \{1^n | \exists x \in B : |x| = n\}</tex>. Ясно, что <tex>\forall B \Rightarrow 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>M_i</tex>. Построение множества <tex>B</tex> разделим на счетное число стадий, на каждой из которых множество пополнится конечным числом элементов. Будем строить <tex>B</tex> так, чтобы на <tex>i</tex>-й стадии было выполнено: <tex>T(M_i, x) \ge 2^{|x|-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>i</tex>-й стадии было выполнено: <tex>M_i</tex> не распознает язык <tex>U_B</tex> за время не большее, чем <tex>2^{n-1}</tex>.  Очевидно, что это утверждение сильнее, чем <tex>U_B \not\in \mathrm{P^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> следующим образом:
Строка 36: Строка 36:
 
** если принадлежность <tex>x</tex> множеству <tex>B</tex> не установлена ранее, то далее считаем, что <tex>x \not\in 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>2^{n-1}</tex> шагов и вернуть какое-либо значение. Так как <tex>B</tex> строится с условием <tex>M_i</tex> не распознает <tex>U_B</tex> за время <tex>2^{n-1}</tex>, то решение машины о принадлежности слова должно быть неверным:
 
* если <tex>M_i</tex> приняла слово, то исключим из <tex>B</tex> все слова вида <tex>\{0,1\}^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</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.
 
* Если <tex>M_i</tex> отклонила слово, то выберем слово <tex>x</tex> длины <tex>n</tex>, принадлежность которого <tex>B</tex> еще не определено. Добавим <tex>x</tex> в <tex>B</tex>. Такое слово всегда найдется, так как на предыдущий шагах мы могли сделать не более, чем <tex>2^n-1</tex> запросов к оракулу (то есть определить принадлежность <tex>B</tex> не более <tex>2^n-1</tex> слов длины <tex>n</tex>), а всего слов длины n <tex>2^n</tex>.
  
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.
+
Во множестве <tex>B</tex> на каждой стадии содержится конечное число элементов, так как на каждой стадии в <tex>B</tex> может быть добавлено не более чем <tex>2^{n-1}+1</tex> слов.  
  
Рассмотрим построенное по описанному выше алгоритму множество <tex>B</tex>. Предположим, что <tex>M_i</tex> отработала менее, чем за время <tex>2^{n-1}</tex>, на слове <tex>1^n</tex>, где <tex>n</tex> определено для каждого <tex>i</tex> в алгоритме, описанном выше. Тогда
+
Из построения получаем, что никакая машина не может распознать <tex>U_B</tex> за время <tex>2^{n-1}</tex>. Следовательно, <tex>U_B \not\in \mathrm{P_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-1}</tex>.
 
 
}}
 
}}
  

Версия 23:45, 15 мая 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]

Рассмотрим 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] \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]B[/math]

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

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

Во множестве [math]B[/math] на каждой стадии содержится конечное число элементов, так как на каждой стадии в [math]B[/math] может быть добавлено не более чем [math]2^{n-1}+1[/math] слов.

Из построения получаем, что никакая машина не может распознать [math]U_B[/math] за время [math]2^{n-1}[/math]. Следовательно, [math]U_B \not\in \mathrm{P_B}[/math].
[math]\triangleleft[/math]

Следствия

Утверждение:
Методом диагонализации нельзя доказать, что [math]\mathrm{P} \neq \mathrm{NP}[/math].
Утверждение:
Никакой метод, который использует операции релятивизации, не может сказать равны ли [math]\mathrm{P}[/math] и [math]\mathrm{NP}[/math].