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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Формулировка)
(не показана 1 промежуточная версия 1 участника)
Строка 7: Строка 7:
 
1)<tex>A</tex>=<tex>TQBF</tex>
 
1)<tex>A</tex>=<tex>TQBF</tex>
  
  <tex>NP^{TQBF}\subset{NPS^{TGBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}</tex>
+
  <tex>NP^{TQBF}\subset{NPS^{TQBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}</tex>
  
 
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>
 
2) <tex>B</tex>:<tex>L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}</tex>
 +
 +
Будем строить B такое, чтобы для всех М.Т. из Р с оракулом С, данная машина тьюринга "ошибалась" на входе некоторой длины, при ответе на вопрос, есть ли в B слово той же длины, что и вход.
 +
 +
Положим множество B  пустым.
 +
1. Переберем все машины тьюринга. Их счетное множество, каждая работает за полином.
 +
2. Для текущей МТ найдем первую длину i, такую что для всех слов длины не менее i ни одна из уже отработавших МТ ничего не спрашивала про них у оракула.
 +
3. Опишем поведение подходящего оракула. Пусть, если МТ М запущена на длине i, и задает вопросы оракулу C. Если М спросит С про слово длины не менее i, С должен ответить 0, одновременно запомнив, что это слово никогда не должно оказаться в В. Если же М спросит про уже включенные в В слова, С должен ответить 1.
 +
4. Теперь заметим, что так как М работает за полином, а ни про одно слово из i ничего не известно, то М не успеет спросить про все слова длины i, их экспоненциальное количество, значит будет хотя бы одно слово длины i, про которое М не спросит. Теперь, если М ответит 1, то нужно чтобы в В не было ни одного слова длины i, иначе - добавим в B первое в лексикографическом порядке слово из В длины i, про которое М не спрашивала.
 +
5. вернемся на шаг 1.
 +
 +
готово, построено множество слов В, такое что ни одна машина тьюринга из P с оракулом не сможет разрешить, но очевидно, что это множество из NP с оракулом

Версия 15:54, 17 июня 2010

Формулировка

[math]\exists{}[/math] оракулы [math]A[/math] и [math]B[/math] такие что

[math]P^A=NP^A[/math] [math]P^B\ne{}NP^B[/math]

1)[math]A[/math]=[math]TQBF[/math]

[math]NP^{TQBF}\subset{NPS^{TQBF}}=PS^{TQBF}=PS\subset{P^{TQBF}\subset{NP^{TQBF}}}[/math]

2) [math]B[/math]:[math]L_B=\{x|\exists{y}\subset{B}:|x|=|y|\}[/math]

Будем строить B такое, чтобы для всех М.Т. из Р с оракулом С, данная машина тьюринга "ошибалась" на входе некоторой длины, при ответе на вопрос, есть ли в B слово той же длины, что и вход.

Положим множество B пустым. 1. Переберем все машины тьюринга. Их счетное множество, каждая работает за полином. 2. Для текущей МТ найдем первую длину i, такую что для всех слов длины не менее i ни одна из уже отработавших МТ ничего не спрашивала про них у оракула. 3. Опишем поведение подходящего оракула. Пусть, если МТ М запущена на длине i, и задает вопросы оракулу C. Если М спросит С про слово длины не менее i, С должен ответить 0, одновременно запомнив, что это слово никогда не должно оказаться в В. Если же М спросит про уже включенные в В слова, С должен ответить 1. 4. Теперь заметим, что так как М работает за полином, а ни про одно слово из i ничего не известно, то М не успеет спросить про все слова длины i, их экспоненциальное количество, значит будет хотя бы одно слово длины i, про которое М не спросит. Теперь, если М ответит 1, то нужно чтобы в В не было ни одного слова длины i, иначе - добавим в B первое в лексикографическом порядке слово из В длины i, про которое М не спрашивала. 5. вернемся на шаг 1.

готово, построено множество слов В, такое что ни одна машина тьюринга из P с оракулом не сможет разрешить, но очевидно, что это множество из NP с оракулом