Редактирование: Сложностный класс BPP

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 14: Строка 14:
  
 
==Эквивалентность определений==
 
==Эквивалентность определений==
Требуется доказать, что <tex>BPP_{strong} = BPP= BPP_{weak}</tex>.<br>
+
Требуется доказать, что <math>~BPP_{strong} = BPP= BPP_{weak}</math>.<br>
 
Для доказательства обоих равенств потребуется неравенство Чернова:<br>
 
Для доказательства обоих равенств потребуется неравенство Чернова:<br>
<center><tex>\forall p > 1/2: \sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}</tex></center>
+
<center><math>\forall p > 1/2:~ \sum_{\mathcal{b}\frac{n}{2}\mathcal{c}+1}^{n}[{{{n\choose i}} p^{i}(1-p)^{n-i}] \geq 1 - e^{-2n(p-1/2)^2}}</math></center>
  
===Доказательство <tex>BPP_{strong} = BPP</tex>===
+
===Доказательство <math>~BPP_{strong} = BPP</math>===
Очевидно, что <tex>BPP_{strong} \subset BPP</tex>.<br>
+
Очевидно, что <math>~BPP_{strong} \subset BPP</math>.<br>
Докажем обратное включение. Пусть <tex>L \in BPP</tex>, тогда существует
+
Докажем обратное включение. Пусть <math>L \in BPP</math>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{1}: T(m_{1},x) = Poly(|x|) \wedge P(m_{1}(x) = [x \in L]) > 2/3</tex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{2}: T(m_{2},x) = Poly(|x|) \wedge P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)}</tex>,
+
[[Вероятностная машина Тьюринга|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) > 2/3</math>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)}</math>,
используя заданные <tex>m_{1}</tex> и <tex>p(|x|)</tex>. Если нам это удастся, то <tex>L \in BPP_{strong} \Rightarrow BPP \subset BPP_{strong} \Rightarrow BPP_{strong} = BPP</tex>.
+
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP_{strong} \Rightarrow BPP \in BPP_{strong} \Rightarrow ~BPP_{strong} = BPP</math>.
====Построение <tex>m_{2}</tex>====
+
====Построение <math>~m_{2}</math>====
Машина <tex>m_{2}</tex> будет работать таким образом:
+
Машина <math>m_{2}</math> будет работать таким образом:
запустим <tex>N_{str}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
+
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
+
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.
Если <tex>N_{str}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \wedge N_{str} \in poly(|x|)</tex>, то искомая машина построена.
+
Если <math>N_{str}</math> таково, что <math>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \and N_{str} \in poly(|x|)</math>, то искомая машина построена.
=====Построение <tex>N_{str}(p|x|,m_{1})</tex>=====
+
=====Построение <math>~N_{str}(p|x|,m_{1})</math>=====
При запуске машины <tex>m_{2}</tex> все запуски <tex>m_{1}</tex> можно считать независимыми, причем каждый запуск
+
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск
<tex>m_{1}</tex> возвращает правильный ответ с вероятностью <tex>p \geq 2/3 > 1/2</tex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <tex>P(m_{2}(x) = [x \in L])</tex>:<br>
+
<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p \geq 2/3 > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
<tex>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{str}}{2}\mathcal{c}+1}^{N_{str}}[{N_{str}\choose i} p^{i}(1-p)^{N_{str}-i}]</tex>. Тогда, по неравенству Чернова: <tex>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</tex>. Достаточно подобрать такое <tex>N_{str}</tex>, чтобы <tex>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(|x|)}</tex>. Несложными преобразованиями получаем <tex>N_{str} \geq \frac{p(|x|) \ln 2}{2(p-1/2)^2}</tex>, т.е. можем выбрать <tex>N_{str} \in poly(|x|)</tex>
+
<math>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{str}}{2}\mathcal{c}+1}^{N_{str}}[{N_{str}\choose i} p^{i}(1-p)^{N_{str}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{str}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{str}</math>, чтобы <math>1 - e^{-2N_{str}(p-1/2)^2} \geq 1 - 2^{-p(|x|)}</math>. Несложными преобразованиями получаем <math>N_{str} \geq \frac{p(|x|) \ln 2}{2(p-1/2)^2}</math>, т.е. можем выбрать <math>N_{str} \in poly(|x|)</math>
  
  
===Доказательство <tex>BPP_{weak} = BPP</tex>===
+
===Доказательство <math>~BPP_{weak} = BPP</math>===
Очевидно, что <tex>BPP \subset BPP_{weak}</tex>.<br>
+
Очевидно, что <math>~BPP \subset BPP_{weak}</math>.<br>
Докажем обратное включение. Пусть <tex>L \in BPP_{weak}</tex>, тогда существует
+
Докажем обратное включение. Пусть <math>L \in BPP_{weak}</math>, тогда существует
[[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{1}: T(m_{1},x) = Poly(|x|) \wedge P(m_{1}(x) = [x \in L]) >  1/2 + 1/p(|x|)</tex>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <tex>m_{2}: T(m_{2},x) = Poly(|x|) \wedge P(m_{2}(x) = [x \in L]) >2/3</tex>,
+
[[Вероятностная машина Тьюринга|ВМТ]] <math>m_{1}: T(m_{1},x) = Poly(|x|) \and P(m_{1}(x) = [x \in L]) >  1/2 + 1/p(|x|)</math>. Построим [[Вероятностная машина Тьюринга|ВМТ]] <math>m_{2}: T(m_{2},x) = Poly(|x|) \and P(m_{2}(x) = [x \in L]) >2/3</math>,
используя заданные <tex>m_{1}</tex> и <tex>p(|x|)</tex>. Если нам это удастся, то <tex>L \in BPP \Rightarrow BPP_{weak} \subset BPP \Rightarrow BPP_{weak} = BPP</tex>.
+
используя заданные <math>m_{1}</math> и <math>~p(|x|)</math>. Если нам это удастся, то <math>L \in BPP \Rightarrow BPP_{weak} \in BPP \Rightarrow ~BPP_{weak} = BPP</math>.
====Построение <tex>m_{2}</tex>====
+
====Построение <math>~m_{2}</math>====
Машина <tex>m_{2}</tex> будет работать таким образом:
+
Машина <math>m_{2}</math> будет работать таким образом:
запустим <tex>N_{weak}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
+
запустим <math>~N_{str}(p(|x|),m_{1})</math> раз машину <math>m_{1}</math>, запоминая результат каждого запуска.
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
+
Вернем <math>1</math>, если больше половины запусков вернули <math>1</math>. Иначе вернем <math>0</math>.
Если <tex>N_{weak}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) > 2/3) \wedge N_{weak} \in poly(|x|)</tex>, то искомая машина построена.
+
Если <math>N_{weak}</math> таково, что <math>P(m_{2}(x) = [x \in L]) > 2/3) \and N_{weak} \in poly(|x|)</math>, то искомая машина построена.
=====Построение <tex>N_{weak}(p|x|,m_{1})</tex>=====
+
=====Построение <math>~N_{weak}(p|x|,m_{1})</math>=====
При запуске машины <tex>m_{2}</tex> все запуски <tex>m_{1}</tex> можно считать независимыми, причем каждый запуск
+
При запуске машины <math>m_{2}</math> все запуски <math>m_{1}</math> можно считать независимыми, причем каждый запуск
<tex>m_{1}</tex> возвращает правильный ответ с вероятностью <tex>p = 1/2 + 1/p(|x|) > 1/2</tex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <tex>P(m_{2}(x) = [x \in L])</tex>:<br>
+
<math>m_{1}</math> возвращает правильный ответ с вероятностью <math>p = 1/2 + 1/p(|x|) > 1/2</math>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <math>P(m_{2}(x) = [x \in L])</math>:<br>
<tex>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</tex>. Тогда, по неравенству Чернова: <tex>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</tex>. Достаточно подобрать такое <tex>N_{weak}</tex>, чтобы <tex>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</tex>. Несложными преобразованиями получаем <tex>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}</tex>, т.е. можем выбрать <tex>N_{weak} \in poly(|x|)</tex>.
+
<math>P(m_{2}(x) = [x \in L]) = \sum_{\mathcal{b}\frac{N_{weak}}{2}\mathcal{c}+1}^{N_{weak}}[{N_{weak}\choose i} p^{i}(1-p)^{N_{weak}-i}]</math>. Тогда, по неравенству Чернова: <math>P(m_{2}(x) = [x \in L]) \geq 1 - e^{-2N_{weak}(p-1/2)^2}</math>. Достаточно подобрать такое <math>N_{weak}</math>, чтобы <math>1 - e^{-2N_{weak}(p-1/2)^2} \geq 2/3</math>. Несложными преобразованиями получаем <math>N_{weak} \geq \frac{\ln 3}{2(1/2 +1/p(|x|)-1/2)^2} = \frac{p(|x|)^2 \ln 3}{2}</math>, т.е. можем выбрать <math>N_{weak} \in poly(|x|)</math>.

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)