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ä.)