Сложностный класс BPP — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Определение класса PP)
м (rollbackEdits.php mass rollback)
 
(не показано 20 промежуточных версий 5 участников)
Строка 1: Строка 1:
==Определение класса PP==
+
==Определение класса BPP==
Классом <tex>\mbox{PP}</tex> называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее результат совпадает с принадлежностью входа данным языкам и время ее работы ограничено полиномом от длины входа.
+
Классом <tex>\mbox{BPP}</tex> (от англ. ''bounded-error, probabilistic, polynomial'') называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше <tex>\frac{2}{3}</tex> и время ее работы ограничено полиномом от длины входа.
<tex>\mbox{PP} = \{L \mid \exists m: \mbox{P}(m(x) = [x \in L])\g \frac{1}{2}\}</tex>
+
<tex>\mbox{BPP} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{2}{3} \}</tex>
В этом определениях <tex>m</tex> - это [[Вероятностные машины Тьюринга | вероятностная машина Тьюринга]], время работы которой ограничено полиномом от длины входа.
+
, где <tex>m</tex> - [[Вероятностная машина Тьюринга|вероятностная машина Тьюринга]].
  
==Определение класса BPP==
+
Очевидно, класс <tex>\mbox{BPP} \in \mbox{PP}</tex>.
 +
 
 +
Также существуют два эквивалентных определения <tex>BPP</tex>:
 +
*<tex>\mbox{BPP}_{weak} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > \frac{1}{2} + 1/p(|x|)\}</tex>, где <tex>m</tex> - [[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|): \forall x ~ p(|x|) > 2</tex> - полином.
 +
*<tex>\mbox{BPP}_{strong} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) > 1 - 2^{-p(|x|)}\}</tex>, где <tex>m</tex> - [[Вероятностная машина Тьюринга|ВМТ]], а <tex>p(|x|)</tex> - полином.
 +
 
 +
 
 +
Число <tex>\frac{2}{3}</tex> в определении выбрано произвольно: если вместо него выбрать любое число, строго большее <tex>\frac{1}{2}</tex>, то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки <tex>p</tex>, то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину <tex>k=|x|</tex> раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1-p)} \right)^k</tex>, а время останется равным <tex>poly(|x|)</tex>. Здесь <tex>k</tex> запусков машины рассматриваются как схема Бернулли с <tex>k</tex> испытаниями и вероятностью успеха <tex>1-p</tex>, а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину <tex>k^{2}</tex> раз подряд, то время все еще будет <tex>poly(|x|)</tex>, а вероятность ошибки упадёт до <tex>\left(2 \sqrt{p(1-p)} \right)^{k^2}</tex>. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.
 +
 
 +
==Эквивалентность определений==
 +
Требуется доказать, что <tex>BPP_{strong} = BPP= BPP_{weak}</tex>.<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>
 +
 
 +
===Доказательство <tex>BPP_{strong} = BPP</tex>===
 +
Очевидно, что <tex>BPP_{strong} \subset BPP</tex>.<br>
 +
Докажем обратное включение. Пусть <tex>L \in BPP</tex>, тогда существует
 +
[[Вероятностная машина Тьюринга|ВМТ]] <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>,
 +
используя заданные <tex>m_{1}</tex> и <tex>p(|x|)</tex>. Если нам это удастся, то <tex>L \in BPP_{strong} \Rightarrow BPP \subset BPP_{strong} \Rightarrow BPP_{strong} = BPP</tex>.
 +
====Построение <tex>m_{2}</tex>====
 +
Машина <tex>m_{2}</tex> будет работать таким образом:
 +
запустим <tex>N_{str}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
 +
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
 +
Если <tex>N_{str}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) >1 - 2^{-p(|x|)} \wedge N_{str} \in poly(|x|)</tex>, то искомая машина построена.
 +
=====Построение <tex>N_{str}(p|x|,m_{1})</tex>=====
 +
При запуске машины <tex>m_{2}</tex> все запуски <tex>m_{1}</tex> можно считать независимыми, причем каждый запуск
 +
<tex>m_{1}</tex> возвращает правильный ответ с вероятностью <tex>p \geq 2/3 > 1/2</tex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <tex>P(m_{2}(x) = [x \in L])</tex>:<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>
 +
 
 +
 
 +
===Доказательство <tex>BPP_{weak} = BPP</tex>===
 +
Очевидно, что <tex>BPP \subset BPP_{weak}</tex>.<br>
 +
Докажем обратное включение. Пусть <tex>L \in BPP_{weak}</tex>, тогда существует
 +
[[Вероятностная машина Тьюринга|ВМТ]] <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>,
 +
используя заданные <tex>m_{1}</tex> и <tex>p(|x|)</tex>. Если нам это удастся, то <tex>L \in BPP \Rightarrow BPP_{weak} \subset BPP \Rightarrow BPP_{weak} = BPP</tex>.
 +
====Построение <tex>m_{2}</tex>====
 +
Машина <tex>m_{2}</tex> будет работать таким образом:
 +
запустим <tex>N_{weak}(p(|x|),m_{1})</tex> раз машину <tex>m_{1}</tex>, запоминая результат каждого запуска.
 +
Вернем <tex>1</tex>, если больше половины запусков вернули <tex>1</tex>. Иначе вернем <tex>0</tex>.
 +
Если <tex>N_{weak}</tex> таково, что <tex>P(m_{2}(x) = [x \in L]) > 2/3) \wedge N_{weak} \in poly(|x|)</tex>, то искомая машина построена.
 +
=====Построение <tex>N_{weak}(p|x|,m_{1})</tex>=====
 +
При запуске машины <tex>m_{2}</tex> все запуски <tex>m_{1}</tex> можно считать независимыми, причем каждый запуск
 +
<tex>m_{1}</tex> возвращает правильный ответ с вероятностью <tex>p = 1/2 + 1/p(|x|) > 1/2</tex>. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е <tex>P(m_{2}(x) = [x \in L])</tex>:<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>.

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

Определение класса BPP

Классом [math]\mbox{BPP}[/math] (от англ. bounded-error, probabilistic, polynomial) называется множество языков, для которых существует вероятностная машина Тьюринга такая, что вероятность того, что ее выходное значение совпадает с принадлежностью входа данным языкам больше [math]\frac{2}{3}[/math] и время ее работы ограничено полиномом от длины входа. [math]\mbox{BPP} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt \frac{2}{3} \}[/math] , где [math]m[/math] - вероятностная машина Тьюринга.

Очевидно, класс [math]\mbox{BPP} \in \mbox{PP}[/math].

Также существуют два эквивалентных определения [math]BPP[/math]:

  • [math]\mbox{BPP}_{weak} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt \frac{1}{2} + 1/p(|x|)\}[/math], где [math]m[/math] - ВМТ, а [math]p(|x|): \forall x ~ p(|x|) \gt 2[/math] - полином.
  • [math]\mbox{BPP}_{strong} = \{L ~ | ~ \exists m : \mbox{T}(m,x) = poly(|x|), \mbox{P}(m(x) = [x \in L]) \gt 1 - 2^{-p(|x|)}\}[/math], где [math]m[/math] - ВМТ, а [math]p(|x|)[/math] - полином.


Число [math]\frac{2}{3}[/math] в определении выбрано произвольно: если вместо него выбрать любое число, строго большее [math]\frac{1}{2}[/math], то получится тот же самый класс. Это верно, поскольку если есть машина Тьюринга, распознающая язык с вероятностью ошибки [math]p[/math], то точность можно сколь угодно хорошо улучшить за счёт относительно небольшого прироста времени. Если мы запустим машину [math]k=|x|[/math] раз подряд, а в качестве результата возьмём результат большинства запусков, то вероятность ошибки упадёт до [math]\left(2 \sqrt{p(1-p)} \right)^k[/math], а время останется равным [math]poly(|x|)[/math]. Здесь [math]k[/math] запусков машины рассматриваются как схема Бернулли с [math]k[/math] испытаниями и вероятностью успеха [math]1-p[/math], а формула, выражающая ошибку, — вероятность неудачи не менее чем в половине случаев. Если теперь запустить машину [math]k^{2}[/math] раз подряд, то время все еще будет [math]poly(|x|)[/math], а вероятность ошибки упадёт до [math]\left(2 \sqrt{p(1-p)} \right)^{k^2}[/math]. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.

Эквивалентность определений

Требуется доказать, что [math]BPP_{strong} = BPP= BPP_{weak}[/math].
Для доказательства обоих равенств потребуется неравенство Чернова:

[math]\forall p \gt 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]

Доказательство [math]BPP_{strong} = BPP[/math]

Очевидно, что [math]BPP_{strong} \subset BPP[/math].
Докажем обратное включение. Пусть [math]L \in BPP[/math], тогда существует ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \wedge P(m_{1}(x) = [x \in L]) \gt 2/3[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \wedge P(m_{2}(x) = [x \in L]) \gt 1 - 2^{-p(|x|)}[/math], используя заданные [math]m_{1}[/math] и [math]p(|x|)[/math]. Если нам это удастся, то [math]L \in BPP_{strong} \Rightarrow BPP \subset BPP_{strong} \Rightarrow BPP_{strong} = BPP[/math].

Построение [math]m_{2}[/math]

Машина [math]m_{2}[/math] будет работать таким образом: запустим [math]N_{str}(p(|x|),m_{1})[/math] раз машину [math]m_{1}[/math], запоминая результат каждого запуска. Вернем [math]1[/math], если больше половины запусков вернули [math]1[/math]. Иначе вернем [math]0[/math]. Если [math]N_{str}[/math] таково, что [math]P(m_{2}(x) = [x \in L]) \gt 1 - 2^{-p(|x|)} \wedge N_{str} \in poly(|x|)[/math], то искомая машина построена.

Построение [math]N_{str}(p|x|,m_{1})[/math]

При запуске машины [math]m_{2}[/math] все запуски [math]m_{1}[/math] можно считать независимыми, причем каждый запуск [math]m_{1}[/math] возвращает правильный ответ с вероятностью [math]p \geq 2/3 \gt 1/2[/math]. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е [math]P(m_{2}(x) = [x \in L])[/math]:
[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]


Доказательство [math]BPP_{weak} = BPP[/math]

Очевидно, что [math]BPP \subset BPP_{weak}[/math].
Докажем обратное включение. Пусть [math]L \in BPP_{weak}[/math], тогда существует ВМТ [math]m_{1}: T(m_{1},x) = Poly(|x|) \wedge P(m_{1}(x) = [x \in L]) \gt 1/2 + 1/p(|x|)[/math]. Построим ВМТ [math]m_{2}: T(m_{2},x) = Poly(|x|) \wedge P(m_{2}(x) = [x \in L]) \gt 2/3[/math], используя заданные [math]m_{1}[/math] и [math]p(|x|)[/math]. Если нам это удастся, то [math]L \in BPP \Rightarrow BPP_{weak} \subset BPP \Rightarrow BPP_{weak} = BPP[/math].

Построение [math]m_{2}[/math]

Машина [math]m_{2}[/math] будет работать таким образом: запустим [math]N_{weak}(p(|x|),m_{1})[/math] раз машину [math]m_{1}[/math], запоминая результат каждого запуска. Вернем [math]1[/math], если больше половины запусков вернули [math]1[/math]. Иначе вернем [math]0[/math]. Если [math]N_{weak}[/math] таково, что [math]P(m_{2}(x) = [x \in L]) \gt 2/3) \wedge N_{weak} \in poly(|x|)[/math], то искомая машина построена.

Построение [math]N_{weak}(p|x|,m_{1})[/math]

При запуске машины [math]m_{2}[/math] все запуски [math]m_{1}[/math] можно считать независимыми, причем каждый запуск [math]m_{1}[/math] возвращает правильный ответ с вероятностью [math]p = 1/2 + 1/p(|x|) \gt 1/2[/math]. Тогда по схеме Бернулли вероятность того, что больше половины запусков вернули правильный ответ, т.е [math]P(m_{2}(x) = [x \in L])[/math]:
[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].