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

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

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{Z}\mathrm{P}\mathrm{P}$ to:

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

suma klas $\mathrm{R}\mathrm{P}$ oraz $\mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$ Źle

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

część wspólna klas $\mathrm{R}\mathrm{P}$ oraz $\mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$ Dobrze

Klasa $\mathrm{P}\mathrm{P}$:

jest przydatna z punktu widzenia praktycznego Źle

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

jest nieprzydatna z punktu widzenia praktycznego Dobrze

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

Klasa $\mathrm{B}\mathrm{P}\mathrm{P}$:

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

jest przydatna z punktu widzenia praktycznego Dobrze

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

jest nieprzydatna z punktu widzenia praktycznego Źle

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

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

Problem MAJSAT

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

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

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

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

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

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

$\mathrm{R}\mathrm{P}$ Źle

$\mathrm{c}\mathrm{o}\mathrm{R}\mathrm{P}$ Dobrze

$\mathrm{Z}\mathrm{P}\mathrm{P}$ Źle

$\mathrm{B}\mathrm{P}\mathrm{P}$ Dobrze

$\mathrm{P}\mathrm{P}$ Dobrze

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

$0$ Źle

$\frac{1}{4}$ Dobrze

$\frac{1}{2}$ Źle

$\frac{3}{4}$ Źle

$1$ Źle