Złożoność obliczeniowa/Test 10: Algorytmy probabilistyczne

From Studia Informatyczne

Algorytmy dla języków z klasy \cc{RP}:

mają ograniczone prawdopodobieństwo błędu

działają w czasie oczekiwanym wielomianowym

mogą dawać fałszywe odpowiedzi pozytywne

mogą popełniać błąd dwustronny

mogą dawać fałszywe odpowiedzi negatywne

działają w czasie wielomianowym


Klasa \cc{ZPP} to:

klasa języków posiadających algorytm typu Las Vegas

suma klas \cc{RP} oraz \cc{coRP}

klasa języków posiadających algorytm typu Monte Carlo

część wspólna klas \cc{RP} oraz \cc{coRP}


Klasa \cc{PP}:

jest przydatna z punktu widzenia praktycznego

zawiera w sobie klasę \cc{NP.}

jest nieprzydatna z punktu widzenia praktycznego

jest zawarta w klasie \cc{NP.}


Klasa \cc{BPP}:

zawiera w sobie klasę \cc{NP.}

jest przydatna z punktu widzenia praktycznego

zawiera w sobie klasę \cc{PP}

jest nieprzydatna z punktu widzenia praktycznego

jest zawarta w klasie \cc{PP}

jest zawarta w klasie \cc{NP.}


Problem MAJSAT

jest problemem z klasy \cc{NP.}

polega na stwierdzeniu czy większość możliwych wartościowań formuły jest spełniająca

jest problemem z klasy \cc{PP}

polega na znalezieniu największego leksykograficznie wartościowania spełniającego

jest problemem zupełnym z klasy \cc{PP}


Rozpoznawanie liczb pierwszych przy pomocy testu Millera-Rabina jest algorytmem z klasy:

\cc{RP}

\cc{coRP}

\cc{ZPP}

\cc{BPP}

\cc{PP}


Prawdopodobieństwo błędu jednej iteracji testu Millera-Rabina wynosi:

0

1\over4

1\over2

3\over4

1