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

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

mają ograniczone prawdopodobieństwo błędu Dobrze

działają w czasie oczekiwanym wielomianowym Źle

mogą dawać fałszywe odpowiedzi pozytywne Źle

mogą popełniać błąd dwustronny Źle

mogą dawać fałszywe odpowiedzi negatywne Dobrze

działają w czasie wielomianowym Dobrze

Klasa $\mathrm {ZPP}$ to:

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

suma klas $\mathrm {RP}$ oraz $\mathrm {coRP}$ Źle

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

część wspólna klas $\mathrm {RP}$ oraz $\mathrm {coRP}$ Dobrze

Klasa $\mathrm {PP}$:

jest przydatna z punktu widzenia praktycznego Źle

zawiera w sobie klasę $\mathrm {NP.}$ Dobrze

jest nieprzydatna z punktu widzenia praktycznego Dobrze

jest zawarta w klasie $\mathrm {NP.}$ Źle

Klasa $\mathrm {BPP}$:

zawiera w sobie klasę $\mathrm {NP.}$ Źle

jest przydatna z punktu widzenia praktycznego Dobrze

zawiera w sobie klasę $\mathrm {PP}$ Źle

jest nieprzydatna z punktu widzenia praktycznego Źle

jest zawarta w klasie $\mathrm {PP}$ Dobrze

jest zawarta w klasie $\mathrm {NP.}$ Źle

Problem MAJSAT

jest problemem z klasy $\mathrm {NP.}$ Źle

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

jest problemem z klasy $\mathrm {PP}$ Dobrze

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

jest problemem zupełnym z klasy $\mathrm {PP}$ Dobrze

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

$\mathrm {RP}$ Źle

$\mathrm {coRP}$ Dobrze

$\mathrm {ZPP}$ Źle

$\mathrm {BPP}$ Dobrze

$\mathrm {PP}$ Dobrze

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

$0$ Źle

$1 \over 4$ Dobrze

$1 \over 2$ Źle

$3 \over 4$ Źle

$1$ Źle