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.
(Idea: Kukin kaavan termi
määrittelee tietyn
toteuttavien totuusarvoasetusten joukon
, ja koko kaavan
toteuttavien asetusten joukko on näiden
-joukkojen yhdiste.
Sovella luentomuistiinpanojen s. 211 esitettyä joukkoyhdisteen kokoa
arvioivaa satunnaisalgoritmia.)
Lisätieto: Voidaan osoittaa, että jos
P
NP, niin toteuttavien asetusten määrää ei voida laskea
tarkasti polynomisessa ajassa.