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

Algorytmy dla języków z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{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 Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{ZPP}} to:

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

suma klas Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{RP}} oraz Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coRP}} Źle

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

część wspólna klas Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{RP}} oraz Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coRP}} Dobrze

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} :

jest przydatna z punktu widzenia praktycznego Źle

zawiera w sobie klasę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP.}} Dobrze

jest nieprzydatna z punktu widzenia praktycznego Dobrze

jest zawarta w klasie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP.}} Źle

Klasa Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{BPP}} :

zawiera w sobie klasę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP.}} Źle

jest przydatna z punktu widzenia praktycznego Dobrze

zawiera w sobie klasę Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} Źle

jest nieprzydatna z punktu widzenia praktycznego Źle

jest zawarta w klasie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} Dobrze

jest zawarta w klasie Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP.}} Źle

Problem MAJSAT

jest problemem z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{NP.}} Źle

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

jest problemem z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} Dobrze

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

jest problemem zupełnym z klasy Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} Dobrze

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

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{RP}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{coRP}} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{ZPP}} Źle

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{BPP}} Dobrze

Parser nie mógł rozpoznać (nieznana funkcja „\cc”): {\displaystyle \cc{PP}} 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