BPL (složitost) - BPL (complexity)
v teorie výpočetní složitosti, BPL (Pravděpodobnostní logaritmický prostor s ohraničenou chybou),[1] někdy volal BPLP (Pravděpodobnostní logaritmicko-prostorový polynomiální čas s ohraničenou chybou),[2] je třída složitosti problémů řešitelných v logaritmický prostor a polynomiální čas s pravděpodobnostní Turingovy stroje s oboustranná chyba. Je pojmenován analogicky s BPP, který je podobný, ale nemá žádné logaritmické omezení prostoru.
Chybový model
Pravděpodobnostní Turingovy stroje v definici BPL smí přijmout nebo odmítnout pouze nesprávně méně než 1/3 času; tomu se říká oboustranná chyba. Konstanta 1/3 je libovolná; žádný X s 0 ≤ X <1/2 by stačilo. K této chybě může dojít 2−str(X) krát menší pro libovolný polynom str(X) bez použití více než polynomiálního času nebo logaritmického prostoru opakovaným spuštěním algoritmu.
Související třídy
Protože oboustranná chyba je obecnější než jednostranná chyba, RL a jeho doplněk co-RL jsou obsaženy v BPL. BPL je také obsažen v PL, což je podobné, až na to, že chyba je omezena na 1/2, místo konstanty menší než 1/2; jako třída PP, třída PL je méně praktické, protože ke snížení pravděpodobnosti chyby na malou konstantu může vyžadovat velký počet kol.
Nisan (1994) ukázal slabý derandomizace vyústit v to BPL je obsažen v SC.[3] SC je třída problémů řešitelných v polynomiálním čase a polylogaritmickém prostoru na deterministickém Turingově stroji; jinými slovy, tento výsledek ukazuje, že daný polylogaritmický prostor, může deterministický stroj simulovat logaritmický prostorové pravděpodobnostní algoritmy.
BPL je obsažen v NC a v DSPACE(log3/2 n) [4] a v L / poly.
Reference
- ^ „Složitost Zoo: BPL“. Archivovány od originál dne 2012-08-05. Citováno 2011-10-04.
- ^ Borodin, A.; Cook, S.A.; Dymond, P. W .; Ruzzo, W. L .; Tompa, M. (1989), „Dvě aplikace indukčního počítání pro problémy s komplementací“, SIAM Journal on Computing, 18 (3): 559–578, CiteSeerX 10.1.1.394.1662, doi:10.1137/0218038
- ^ Nisan, N. (1994), „RL ⊆ SC“, Výpočetní složitost, 4 (1): 1–11, doi:10.1007 / BF01205052 „Starší verze tohoto článku se objevila v roce 1992 Symposium on Theory of Computing
- ^ Poznámky k přednášce teorie složitosti