Atsitiktiniai skaičiavimai su ribota klaidos tikimybe
Atsitiktiniai pasirinkimai leidžia turėti nurodytą klaidos tikimybę.
Esminės žinios
BPP sudaro sprendimo uždavinių kalbos, kurioms yra tikimybinis polinominio laiko algoritmas, kiekvienai įvesčiai klystantis ne didesne kaip 1/3 tikimybe. Nepriklausomi kartojimai ir balsavimas dauguma sumažina fiksuotą klaidos tikimybę, mažesnę už 1/2, iki bet kurios pasirinktos teigiamos konstantos.
Sąlygos ir taikymo ribos
- Tikimybė apibrėžta pagal algoritmo atsitiktinius pasirinkimus, o ne pagal įvesčių skirstinį.
- Teigiamos ribotos klaidos garantija vien dėl baigtinio kartojimų skaičiaus netampa tiksliai nuline klaida.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
BPP apibrėžimas, fizinis puslapis 8; nepriklausomi kartojimai ir klaidos tikimybės mažinimas puslapiuose 12–14; skaidrės lemos nulinės klaidos ribinis atvejis neįtrauktas.
2026-10-10 · BPP ir ribotos klaidos tikimybės mažinimas; skaidrės lemos nulinės klaidos ribinis atvejis neįtrauktas.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-randomized-algorithms
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas