BPP (složitost)
V teoretické informatiky , zejména v teorii složitosti se třídou BPP ( ohraničené-error pravděpodobnostní polynomial čas) je třída z rozhodovacích problémů rozhodnuto o pravděpodobnostní Turingova stroje v časové polynomu , s pravděpodobností chyby v odpovědi méně než 1/3 .
Definice
První definice
Třída BPP je soubor problémů nebo ekvivalentním způsobem jazyků , pro které existuje pravděpodobnostní Turingův stroj v polynomiálním čase, který splňuje následující podmínky přijetí:
- Pokud slovo není v jazyce, zařízení jej odmítne s pravděpodobností větší než 2/3.
- Pokud je slovo v jazyce, zařízení jej přijme s pravděpodobností větší než 2/3.
Jinými slovy, stroj se mýlí s pravděpodobností menší než 1/3.
Formální definice
Třídu BPP definujeme jako sadu jazyků , takže pro každé slovo existuje polynom a jazyk, který toto ověřuje :
L{\ displaystyle L}p(ne){\ displaystyle p (n)}NA∈P{\ displaystyle A \ in {\ rm {P}}}X{\ displaystyle x}
-
X∈L⇒Prε∈{0,1}p(|X|)((X,ε)∈NA)≥23{\ displaystyle x \ v L \ Rightarrow {\ podmnožina {\ varepsilon \ v \ {0,1 \} ^ {p (| x |)}} {Pr}} ((x, \ varepsilon) \ v A) \ geq {\ frac {2} {3}}}.
-
X∉L⇒Prε∈{0,1}p(|X|)((X,ε)∈NA)≤13{\ displaystyle x \ notin L \ Rightarrow {\ podmnožina {\ varepsilon \ in \ {0,1 \} ^ {p (| x |)}} {Pr}} ((x, \ varepsilon) \ v A) \ leq {\ frac {1} {3}}}.
Vztahy s ostatními třídami
Deterministický versus pravděpodobnostní polynomiální čas
Můžeme použít pravděpodobnostní stroj k provedení deterministického výpočtu, a proto P BPP . Druhé zahrnutí je otevřená otázka. Obecněji řečeno, otázkou je, zda je náhodnost užitečná pro urychlení výpočtu nebo ne. Komplexní komunita na toto téma změnila názor: až do 80. let si většina vědců myslela, že BPP se liší od P, a pak různé výsledky tuto víru narušily. Dnes se často uvažuje o kravatě.
⊆{\ displaystyle \ scriptstyle \ subseteq}
Jiné vztahy
BPP také obsahuje pravděpodobnostní třídy, jejichž podmínky přijetí jsou silnější ZPP , RP a co-RP .
S notacemi polynomiální hierarchie máme podle věty Sipser - Gács - Lautemann .
BPP⊆Σ2p∩Π2p{\ displaystyle BPP \ subseteq \ Sigma _ {2} ^ {p} \ cap \ Pi _ {2} ^ {p}}
Ve světě booleovských tříd obvodů dává Adlemanova věta BPP P / poly ( Adleman 1978 ).
⊆{\ displaystyle \ scriptstyle \ subseteq}
Kvantová varianta BPP je BQP .
Vlastnosti a věty
- V případě potřeby můžeme mít efektivnější stroje, jinými slovy můžeme nahradit 2/3 za a 1/3 za (pro velmi mladé), aniž bychom změnili třídu. Toto posílení lze provést samostatným házením stroje několikrát a hlasováním. Výpočet využívá Chernoffovy meze .1-ϵ{\ displaystyle 1- \ epsilon}ϵ{\ displaystyle \ epsilon}ϵ{\ displaystyle \ epsilon}
- BPP je uzavřen doplňkovým, tj. BPP = co-BPP.
Dějiny
Tuto třídu představil J. Gill v článku Výpočetní složitost pravděpodobnostních Turingových strojů , současně s třídami RP a ZPP .
Bibliografie
Externí odkaz
Poznámky a odkazy
-
Sylvain Perifel , Algoritmická složitost , Elipsy ,2014, 432 s. ( ISBN 9782729886929 , číst online ) , kap. 12.1 („Derandomizace“)p. 318.
-
(in) Sanjeev Arora a Boaz Barak , Výpočetní složitost: moderní přístup , Cambridge University Press ,2009( ISBN 0-521-42426-7 ) , kap. 7část 5.2 BPP je v PH
-
Složitost Zoo
-
(in) John Gill , „ Výpočetní složitost pravděpodobnostního Turingova stroje “ , SIAM Journal we Computing , roč. 6, n O 4,
1977, str. 675-695
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">