Sanotaan, että Monte Carlo -tyyppinen satunnaisalgoritmi A on luotettava, jos se annetulla syötteellä antaa oikean vastauksen todennäköisyydellä p > 0, ja todennäköisyydellä q = 1-p vastaa ``en tiedä''. Mikä on oikean vastauksen todennäköisyys, kun algoritmi A suoritetaan k kertaa peräkkäin? (Oletetaan, että suorituskerrat ovat toisistaan riippumattomia, ja toisto lopetetaan heti kun oikea vastaus on saatu.) Montako kertaa algoritmia tarvitsee enintään toistaa, jotta oikean vastauksen todennäköisyys saataisiin suuremmaksi kuin , jollakin annetulla ?
missä kukin termi on literaalien konjunktio
(Tässä siis kukin on joko muuttuja tai sellaisen negaatio.) Laadi satunnaisalgoritmi, joka arvioi monellako muuttujien totuusarvoasetuksella annettu dnf-muotoinen kaava tulee todeksi. (Vihje: Kukin kaavan termi määrittelee tietyn toteuttavien totuusarvoasetusten joukon , ja koko kaavan toteuttavien asetusten joukko on näiden -joukkojen yhdiste.) Lisätieto: Toteuttavien asetusten tarkan määrän laskeminen on ns. #P-täydellinen ongelma, siis luultavasti ei tehtävissä polynomisessa ajassa. (Funktio kuuluu luokkaan #P, jos jollakin epädeterministisellä polynomisessa ajassa toimivalla Turingin koneella M on f(x) = M:n syötteellä x hyväksyvien laskentojen määrä.)