BPP osztály

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. augusztus 10-én felülvizsgált verziótól ; az ellenőrzések 2 szerkesztést igényelnek .

Az algoritmusok elméletében a BPP komplexitási osztály (az angol bounded-error, probabilistic, polynomial szóból ) a predikátumok osztálya , gyorsan (polinomiális időben) kiszámítható és nagy valószínűséggel ad választ (sőt, időt feláldozva, tetszőlegesen nagy válaszpontosság elérése). Valószínűségi módszerekkel megoldott és BPP-ben való hazudozással megoldott problémák nagyon gyakran merülnek fel a gyakorlatban.

Formális definíció

A BPP osztály a P(x) predikátumok osztálya, amelyek valószínűségi Turing-gépeken (közönséges Turing-gépeken véletlenszám-szalaggal) számíthatók ki polinomiális időben, legfeljebb ⅓ hibával. Ez azt jelenti, hogy a predikátum értékét kiszámító valószínűségi Turing-gép O(n k ) -vel egyenlő választ ad időben , ahol n x hossza , és ha a helyes válasz 1, akkor a gép 1-et ad legalább ⅔ valószínűséggel , és fordítva. A szavak halmazát , amelyre P(x) 1-et ad vissza, a P(x) predikátum által felismert nyelvnek nevezzük .

A definícióban a ⅓ számot tetszőlegesen választjuk: ha helyette bármely p számot választunk , amely szigorúan kisebb, mint ½, akkor ugyanazt az osztályt kapjuk. Ez azért igaz, mert ha van olyan Turing-gép, amely O(n k ) idő alatt p hibavalószínűségű nyelvet ismer fel , akkor viszonylag kis időnövekedéssel tetszőlegesen jól javítható a pontosság. Ha a gépet n -szer futtatjuk egymás után, és a legtöbb futás eredményét vesszük eredményül, akkor a hiba valószínűsége -re csökken , és az idő O(n k+1 ) lesz . Itt a gép n futtatását Bernoulli-sémaként kezeljük, n próbával és 1-p siker valószínűséggel, a hibaképlet pedig a meghibásodás valószínűsége legalább fele. Ha most 2 -szer egymás után futtatjuk az n gépet , akkor az idő O(n k+2 ) -ra nő , és a hiba valószínűsége -ra csökken . Így az időbecslő polinom kitevőjének növekedésével a pontosság exponenciálisan nő , és bármilyen kívánt érték elérhető. $\left(2{\sqrt {p(1-p)}}\jobb)^{n}$ $\left(2{\sqrt {p(1-p)}}\right)^{{n^{2}}}$

Monte Carlo algoritmusok

Egy valószínűségi algoritmus a Monte Carlo-szabvány szerinti nyelvet veszi át, ha az algoritmus hibavalószínűsége nem haladja meg a -t . Vagyis hol van az állítmány, hogy a szó a nyelvhez tartozik . Így a BPP osztályt predikátumok alkotják úgy, hogy létezik egy polinomiális valószínűségi algoritmus, amely a nyelvüket a Monte Carlo-szabvány szerint veszi fel. Az ilyen algoritmusokat Monte Carlo algoritmusoknak is nevezik. ${\mathcal {A}}$ $L$ $1/3$ $\mathbb {P} ({\mathcal {A}}(x)=P(x))\geq 2/3$ $P(x)$ $x$ $L$

Kapcsolat Las Vegas-i algoritmusokkal

Legyen az időbonyolultságú Monte Carlo algoritmus , ahol a bemeneti hossz. Alsó korlátnak tekintjük azt a valószínűséget is , hogy a Las Vegas-i algoritmus a megfelelő eredményt adja, valamint egy időbonyolultságú algoritmust , amely ellenőrzi az eredmény megbízhatóságát. Ilyen esetben van egy algoritmus várható időbonyolítással . Ennek bizonyításához képzelje el, mi okozza , és amíg meg nem erősíti az eredmény helyességét. Ekkor egy ilyen eljárás egy iterációjának futási ideje . Az iterációk megismétlődésének valószínűsége , ami azt jelenti, hogy az iterációk várható száma az alapján, hogy . ${\mathcal {B}}$ $f(n)$ $p(n)$ $\mathcal{A}$ ${\mathcal {C}}$ $g(n)$ $\mathcal{A}$ $\mathcal{A}$ ${\megjelenítési stílus (f(n)+g(n))/p(n)}$ $\mathcal{A}$ ${\mathcal {B}}$ ${\mathcal {C}}$ ${\mathcal {C}}$ $f(n)+g(n)$ $k$ $(1-p(n))^{k-1}\cdot p(n)$ $\sum _{k=1}^{\infty }k\cdot (1-p(n))^{k-1}\cdot p(n)=1/p(n)$ ${\displaystyle \sum _{k=1}^{\infty }k\cdot x^{k}=x/(1-x)^{2))$

Kapcsolatok más osztályokkal

Maga a BPP kiegészítés alatt van. A P osztály azért szerepel a BPP-ben, mert polinomiális időben ad választ nulla hibával. A BPP benne van a polinomiális hierarchia osztályban , és ennek eredményeként szerepel a PH és a PSPACE osztályokban . Az is ismert, hogy a BPP-t a P/Poly osztályba sorolják . $\Sigma _{2}^{p}\cap \Pi _{2}^{p}$

A BPP osztály kvantum megfelelője (más szóval a BPP osztály kiterjesztése a kvantumszámítógépekre ) a BQP osztály .

{\mbox{BPP}}\subseteq {\mbox{BQP}}

Egyéb tulajdonságok

2002- ig a BPP osztályban rejlő egyik legismertebb probléma a prímszám-felismerési probléma volt, amelyre többféle polinomiális valószínűségi algoritmus létezett, mint például a Miller-Rabin teszt , de egyik sem volt determinisztikus. 2002-ben azonban egy determinisztikus polinomiális algoritmust találtak Agrawal, Kayan és Saxena indiai matematikusok, akik ezzel bebizonyították, hogy a prímszám felismerésének problémája a P osztályban rejlik . Javasolt AKS algoritmusuk (amelyet a vezetéknevük első betűiről kaptak) felismeri az n hosszúságú szám elsődlegességét O(n 4 ) időben .

Algoritmusok összetettségi osztályai
Fénynek tekinthető	DLOGTIME AC 0 ACC 0 TC0 [ hu L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP EQP APX
Állítólag nehéz	U.P. NP NP kész co-NP társNP-teljes AM M.A. QMA PH ⊕P PP #P #P- IP_ PSPACE PSPACE-teljes
Nehéznek tartott	LEJÁRATI IDŐ NEXPTIME KIFEJEZÉS 2-EXPTIME ELEMENTARY R PR RE töltse ki újra Co-RE Co-RE-complete ÖSSZES