BPL (złożoność)
W teorii złożoności obliczeniowej BPL (Bounded-error Probabilistic Logarithmic-space), czasami nazywany BPLP (Bounded-error Probabilistic Logarithmic-space Polynomial-time), jest klasą złożoności problemów , które można rozwiązać w przestrzeni logarytmicznej i czasie wielomianowym za pomocą probabilistycznych maszyn Turinga z dwustronny błąd . Jest nazwany analogicznie do BPP , który jest podobny, ale nie ma logarytmicznego ograniczenia przestrzeni.
Model błędu
Probabilistyczne maszyny Turinga w definicji BPL mogą akceptować lub odrzucać błędnie tylko przez mniej niż 1/3 czasu; nazywa się to błędem dwustronnym . Stała 1/3 jest dowolna; wystarczyłoby dowolne x z 0 ≤ x <1/2. Ten błąd można zmniejszyć 2 - p ( x ) razy dla dowolnego wielomianu p ( x ) bez użycia więcej niż czasu wielomianu lub przestrzeni logarytmicznej, uruchamiając algorytm wielokrotnie.
Powiązane zajęcia
Ponieważ błąd dwustronny jest bardziej ogólny niż błąd jednostronny, RL i jego dopełnienie co-RL są zawarte w BPL . BPL jest również zawarte w PL , co jest podobne, z wyjątkiem tego, że granica błędu wynosi 1/2, zamiast stałej mniejszej niż 1/2; podobnie jak klasa PP , klasa PL jest mniej praktyczna, ponieważ może wymagać dużej liczby rund, aby zredukować prawdopodobieństwo błędu do małej stałej.
Nisan (1994) wykazał słaby wynik derandomizacji , że BPL jest zawarte w SC . SC to klasa problemów rozwiązywalnych w czasie wielomianowym i przestrzeni polilogarytmicznej na deterministycznej maszynie Turinga; innymi słowy, wynik ten pokazuje, że przy danej polilogarytmicznej maszyna deterministyczna może symulować algorytmy probabilistyczne w przestrzeni logarytmicznej .
BPL jest zawarte w NC iw L/poly . Saks i Zhou wykazali, że BPL jest zawarty w DSPACE (log 3/2 n), aw 2021 Hoza poprawił to, aby pokazać, że BPL jest zawarty w DSPACE .
