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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 13: Строка 13:
 
Очевидно, класс <tex>\mbox{BPP} \in \mbox{PP}</tex>.
 
Очевидно, класс <tex>\mbox{BPP} \in \mbox{PP}</tex>.
  
Так же еще существуют два [[Класс BPP|эквивалентных]] определения <tex>BPP</tex>:
+
Также существуют два [[Класс BPP|эквивалентных]] определения <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}_{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>\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>\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>. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.

Версия 14:49, 15 апреля 2010

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

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

Но это очень широкий класс, поэтому вводится класс [math]\mbox{BPP}[/math].

Определение класса 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]. Таким образом, с ростом показателя многочлена, оценивающего время, точность растёт экспоненциально, и можно достичь любого нужного значения.