Alternatívne výpočtové modely^ ^
Alternatívne výpočtové modely
Motivácia
existencia veľkej triedy prakticky neriešiteľných (a/e rozhodnutelných) problémov, ktore potrebujeme prakticky riešil;!
Idea
využil! principiýlne ine spôsoby poatania
■ paralelne pocítanie
■ sýbežnosl!
■ kvantove pocítanie
■ molekularne pocítanie
■ nahodnosl!
pomože to ???
IB110 Podzim 2010
1
Alternatívne výpočtové modely^Paralelizmus ^ ^
Alternatívne výpočtové modely
TI Paralelizmus
^Kvantové po HlVIolekuiarne HNahodnostne
IB110 Podzim 2010
2
Alternatívne výpočtové modely^Paralelizmus ^ ^
Princíp paralelizmu
Praktický príklad
A veža o zaklade 1m x 10 m a výšky 1 m; 1 murýr vs 10 murýrov
B veža o zaklade 1m x 1 m a výšky 10 m; 1 murýr vs 10 muraýrov
Jednoduchý program
A X — 3; Y — 4
Varianta B X — 3; Y — X
paralelizovatefné problémy vs vnútorne sekvenčné problémy
IB110 Podzim 2010
3
Alternatívne výpočtový modely^Paralelizmus ^ ^
Paralelne sčitovanie
IB110 Podzim 2010
4
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelné scitovanie
pre sčítanie 1 000 čísel potrebujeme v 1. kroku 500 procesorov v 2. kroku 250 procesorov v 3. kroku 125 procesorov
pri vhodne zvolenej dátovej strukture a organizácii komunikácie mezdi procesormi stací na realizáciu celeho výpoctu práve 500 procesorov
pre scítanie N císel potrebujeme N/2 procesorov a pocet (paralelných) výpoctových krokov je O(log N)
IB110 Podzim 2010
5
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmus - poCet procesorov
pocet procesorov potrebných k realizácii paralelného výpočtu ako funkcia velkosti vstupnej inStancie
(N/2 pre sčítanie N čísel)
je to realisticke?
indikátor, aké veľké vstupy môžeme riešil! s počtom procesorov, ktoré máme k dispozícii
(viz analógia s časovou a priestorovou zložitosiou)
ak pocet procesorov, ktore mame k dispozícii, je mensí, moZeme kombinoval! paralelný a sekvencný prístup
IB110 Podzim 2010
6
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelené triedenie
sekvenčné triedenie zoznamu L spájaním (mergesort) procedúra sort-L
(1) ak L má len 1 prvok, je utriedený
(2) inak
(2.1) rozdel' L na dve polovičky Li a L2
(2.2) sort-Li
(2.3) sort-L2
(2.4) spoj dva utriedene zoznamy do jedneho utriedeneho zoznamu počet vykonaných porovnaní je O(N log N)
IB110 Podzim 2010
7
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelné triedenie
paralelne triedenie zoznamu L spájaním procedúra parallel-sort-L
(1) ak L ma len 1 prvok, je utriedený
(2) inak
(2.1) rozdel' L na dve poloviCký Li a L2
(2.2) súbeZne volaj parallel-sort-L1 a parallel-sort-L2
(2.3) spoj dva utriedene zoznamy do jedneho utriedeneho zoznamu
poCet (paralelných) porovnaní je (predpokladáme, že N je mocninou 2) v 1. kroku N postupností dlzký 1; N/2 procesorov;
spojenie dvoch postupností = 1 porovnanie v 2. kroku N/2 postupností dlzký 2; N/4 procesorov;
spojenie dvoch postupností = 3 porovnania v 3. kroku N/4 postupností dlzký 4; N/8 procesorov;
spojenie dvoch postupností = 7 porovnaní spolu 1 + 3 + 7 + 15+-----h (N - 1) < 2N porovnaní
IB110 Podzim 2010 8
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmus - cas x priestor
konvencia: v kontexte paralelných výpočtov sa pod priestorovou zložitosťou rozumie počet procesorov potrebných k realizácii výpočtu
časová a priestorova zložitost paralelných výpoctov su spolu tesne zviazanáe
zníženie jednej obvykle znamená zvýšenie druhej a naopak
IB110 Podzim 2010
9
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmus - cas x priestor
SEQUENTIAL
PARALLEL
Name	Size (no. of processors)	Time (worst case)	Product (time x size)
Bubblesort	1	0(N2)	
Mergesort	1	0(Nx\ogN)	0(Nx logAO (optimal)
Parallelized mergesort	0(N)	<?(A0	OQP)
Odd-even sorting network	0(Nx(\ogN)2)	0({\ogN)2)	0(Nx (\ogN)4)
"Optimal" sorting network	O(N)	O(logA0	0(Nx\ogN) (optimal)
IB110 Podzim 2010
10
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelne siete
Sposob komunikýcie medzi procesormi
t! sícasný zapis resp. cítanie z pamätoveho miesta ??? v prípade sícasneho zapisu nutnost! strategie riesenia konfliktov
i kazdý procesor je prepojený (moze komunikovat!) len s ohranicením poctom susediacich procesorov;
casto ako specializovaný hardware
IB110 Podzim 2010
11
AIternatívne výpočtový modeIy^ParaIeIizmus ^ ^
Triediaca sieť
IBllO Podzim 2010
l2
Alternatívne výpočtové modely^Paralelizmus ^ ^
Môže paralelizmus riešil: neriešiteľné?
Fakt
Každý paralelný algoritmus sa dá transformoval! na sekvenčný algoritmus.
(každý paralelný krok nahradíme postupnosťou sekvenčných krokov; každý sekvenčný krok výkona prícu jedného procesoru)
Dôsledok
Neexistuej paralelný algoritmus pre nerožhodnutelný problém. (CT hýpoteža sa vžtahuje aj na paralelní výpočtoví modely)
IB110 Podzim 2010 13
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmu a prakticky nerieSiteľne problémy
■ existuju problemý, ktore sá sekvencne praktický neriesitel'na a pritom sá praktický riesitel'ne paralelnými algoritmami?
■ specifikacia pojmu „efektívneho" paralelneho algoritmu ???
IB110 Podzim 2010
14
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmu a prakticky neriešiteľné problémy
■ existujú problémy, ktoré sú sekvenčne prakticky nerieSitelna a pritom sú prakticky riesitel'ne paralelnúmi algoritmami?
■ specifikacia pojmu „efektívneho" paralelneho algoritmu ???
■ pozorovanie: pre problem z triedy NP mame nedeterministicky algoritmus polynomiúlnej casovej zloZitosti;
ak nedeterministicky vyber nahradíme paralelizmom, tak okamzite dostavama polynomialne casovo ohraniceny paralelny algoritmus pre tento problem
■ je to prijateľne riesenie?
IB110 Podzim 2010
14
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmu a prakticky nerieSiteľne problémy
■ existujú problemý, ktore su sekvencne praktický neriesitelna a pritom sú praktický riesitel'ne paralelními algoritmami?
■ specifikacia pojmu „efektívneho" paralelneho algoritmu ???
■ pozorovanie: pre problem z triedý NP mame nedeterministický algoritmus polýnomiúlnej casovej zlozitosti;
ak nedeterministický výber nahradíme paralelizmom, tak okamzite dostavama polýnomialne casovo ohranicený paralelný algoritmus pre tento problem
■ je to prijateľne riesenie?
■ exponencialný pocet procesorov
IB110 Podzim 2010
14
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmu a prakticky nerieSiteľne problemy
■ existujú problemý, ktore sú sekvenčne praktický neriešiteľna a pritom sú praktický riesitelne paralelními algoritmami?
■ specifikacia pojmu „efektívneho" paralelneho algoritmu ???
■ pozorovanie: pre problem z triedý NP mame nedeterministický algoritmus polýnomiúlnej casovej zlozitosti;
ak nedeterministický výber nahradíme paralelizmom, tak okamzite dostavama polýnomialne casovo ohranicený paralelný algoritmus pre tento problem
■ je to prijateľne riesenie?
■ exponencialný pocet procesorov
■ co ak praktický neriesitelný problem nepatrí do NP?
IBii0 Podzim 20i0
14
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelizmu a prakticky nerieSiteľne problemy
■ existujú problemý, ktore sú sekvencne praktický neriesitel'na a pritom sú praktický riesitelne paralelními algoritmami?
■ specifikacia pojmu „efektívneho" paralelneho algoritmu ???
■ pozorovanie: pre problem z triedý NP mame nedeterministický algoritmus polýnomiílnej casovej zlozitosti;
ak nedeterministický výber nahradíme paralelizmom, tak okamzite dostavama polýnomialne casovo ohranicený paralelný algoritmus pre tento problem
■ je to prijateľne riesenie?
■ exponencialný počet procesorov
■ co ak praktický neriesitel'ný problem nepatrí do NP?
■ otazka praktickej implementacie paralelného algoritmu, ktorý ma síce polýnomialnu zlozitost, ale potrebuje exponencialný pocet procesorov (napr. otážka komunikácie)
IB110 Podzim 2010
14
Alternatívne výpočtové modely^Paralelizmus ^ ^
Paralelná výpočtová téza
Časť A
Všetky „rozumné" paralelné výpočtové modely sú polynomiálne ekvivalentné.
Čast B
Paralelný čas je polynomialne ekvivalenty sekvenčnemu času.
Sekvenčný-PSPACE = Paralelný-PT\ME
IB110 Podzim 2010
15
Alternatívne výpočtoví modely^Paralelizmus ^ ^
NC - Nickova trieda
polýnomialne casovo ohranicene paralelne algoritmý nemôzeme povazoval! za praktický pouzitel'ne
zmýslom zavedenia paralelizmu je výrazne redukovat! výpoctový cas
sublineárne algoritmý
Trieda NC
Trieda problemov riesitel'ných paralelnými algoritmami s polýlogaritmickou casovou zlozitosl!ou a polýnomialným poctom procesorov.
Trieda NC je robustnaá
IB110 Podzim 2010
16
Alternatívne výpočtové modely^Paralelizmus ^ ^
Vzťah sekvenčných a paralelných zložitostných tried
NC C P C NP C PSPACE
Otvorené problémy: o žiadnej z inklúzií nie je zname, či je ostra, alebo predstavuje rovnost!
Predpoklady
^ existujú problemy, ktore sú prakticky (sekvenčne) rieSitel'ne, ale nie sú riesitel'ne vel'mi rychlo paralelne s použitím rozumne vel'keho hardwaru
1 existuju problemy, ktore sa dajú riesit (sekvenčne) v polynomialnom čase s vyuzitím nedeterminizmu, ale nie bez neho
existuju problemy, ktore sa dajú riesit! v rozmunom (tj. polynomialnom) sekvenčnom priestore (tj. aj v rozumnom paralelnom čase), ale nie su riesitel'ne v rozumnom sekvenčnom čase bez vyuzitia nedeterminizmu.
IB110 Podzim 2010 17
Alternatívne výpočtove modely^Paralelizmus ^ ^
Vzt'ah sekvenčných a paralelných zloZitostných tried
NC C P C NP C PSPACE
Príklady problemov NC scítat N císel
rozhodnú!;, ci v grafe existuje cesta z vrcholu s do vrcholu P \ NC rozhodnút, ci c je najväcsúm spolocnym delitelom cúsel a,
NP \ P problem Hamiltonovskeho cyklu; splnitel'nost logickej form
PSPACE \ PN slovnyú futbal
IB110 Podzim 2010
18
AIternatívne výpočtový modeIy^Súbeznost ^ ^
Aiternatívne vypoCtove modeiy
Pa
Subeznost
Kvantove Molekular Nahodnost
IB110 Podzim 2010
ig
Alternatívne výpočtové modely ^Súbežnost ^ ^
Súbežnosť
situácie, keď paralelizmus nevyužívame k tomu, aby sme zefektívnili výpočty, ale keď paralelizmus vžnika v realnych aplikaciach
reaktívne a zapuzdrene systemy
Úloha
navrhnut! komunikacne protokolý pre komunikujuce objektý tak, abý splňali pozadovane vlastnosti
ň
Specifikum
ílohou sýstemov nieje najst konkretne riesenie, ale pocítal! (být! funkcný) donekoneScna"
IB110 Podzim 2010
20
Alternatívne výpočtové modely^SúbeZnost ^ ^
Problém hotelovej sprchy
■ na poschodí je len jedna sprcha, na veľmi studenej chodbe
■ každy host sa chce osprchovat!, ale nemože cakat na voľný sprchu na chodbe
ak by ž casu na cas kontroloval, ci je sprcha volna, može nastal! situícia, že sa nikdy neosprchuje
možne riesenie
■ tabul'a pri vstupe do sprchy
■ host pri odchode žo sprchy žmaže ž tabule císlo svojej ižby a napíse na nu císlo nasledujucej ižby (v nejakom fixovanom poradí)
■ každy host ž casu na cas kontroluje, ci je na tabuli napísane císlo jeho ižby a ak íano, osprchuje sa
je to dobré riešenie?
(prázdna izba, práve jedno sprchovanie v cýk/e, ...)
IB110 Podzim 2010 21
Alternatívne výpočtové modely ^Súbežnost ^ ^
Distribuované súbežné systémy
■ (súbežné) komponenty systému sú fyzicky oddelené
■ komponenty vzájomne komunikujU
■ typicky od systemov nepožadujeme vstupno - výstupne chovanie, ale kontinuálnu (neprerusenu, neukončenu) funkcionalitu
■ doležite je chovanie systemu v case
■ okrem požiadavkov na jednotlive komponenty, kladieme na system globalne obmedzujuce podmienky
■ zdieľanie splocnych zdrojov
■ prevencia uviaznutia (vzajomne cakanie, deadlock) m prevencia starnutia procesov (starvation)
(algoritmické) protokoly
IB110 Podžim 2010
22
Alternatívne výpočtový modely^SúbeZnost ^ ^
Problem vzajomneho vylúCenia
zobecnenie problíemu hotelovej sprchý
Problem vzajomneho výlícenia: je daných N procesov, kazdý proces opakovane (v nekonecnom cýkle) výkoníva
■ síkromne aktivitý (proces ich môže výkonívat nezívisle na ostatných procesoch) a
■ kriticke aktivitý (ziadne dva procesý nemôzu sícasne výkonavat svoje kritickíe aktivitý)
IB110 Podzim 2010
23
Alternatívne výpočtove modely^SúbeZnost ^ ^
Protokol pre problem vzajomneho vylUCenia
pre dva procesý P1 a P2
protokol výuzíva 3 premenne
Z globalna premenna (vsetky procesy môžu menit jej hodnotu); nadobuda hodnotý 1 a 2
X1 lokalna premenna procesu P1; nadobuda hodnotý yes a no
X2 lokalna premenna procesu P2; nadobuda hodnotý yes a no
pociatocna hodnota premenných X1 a X2 je no, pociatocna hodnota Z je bud' 1 alebo 2
IB110 Podzim 2010
24
protokolvepre»problem vzajomneno vylúčenia (pre dva procesy)
protokol pre proces P1
(1) opakuj v nekonecnom cýkle
(1.1) výkonaj sukromne aktivitý
(1.2) X1 — yes
(1.3) Z — 1
(1.4) cakaj kým bud'
X2 nenadobudne hodnotu no alebo Z nenadobudne hodnotu 2
(1.5) výkonaj kriticke aktivitý
(1.6) X1 — no
protokol pre proces P2
(1) opakuj v nekonecnom cýkle
(1.1) výkonaj síkromne aktivitý
(1.2) X2 — yes
(1.3) Z — 2
(1.4) cakaj kým bud'
X1 nenadobudne hodnotu no alebo Z nenadobudne hodnotu 1
(1.5) výkonaj kriticke aktivitý
(1.6) X2 — no
korektnost! protokolu vzájomne výlucenie OK starnutie procesu OK uviaznutie OK
IB110 Podzim 2010
25
rrotoKoivepre»proDiem vzajomneno vyiucema (pre N procesov)
protokol pre I-tý pročes P\ (1) opakuj v nekonečnom čýkle
(1.1) výkonaj sukromne aktivitý
(1.2) pre každe J od 1 do N - 1 urob
(1.2.1) X[I] ^ J
(1.2.2) Z[I] ^ I
(1.2.3) čakaj kým buď
X [K] < J pre nejake K = I alebo
Z [J] = I
(1.5) výkonaj kritičke aktivitý
(1.6) X [I ] ^ 0
IB110 Podzim 2010
26
Alternatívne výpočtove modely^SúbeZnost ^ ^
Vlastnosti distribuovaných súbeZných systemov
distribuovane súbezne systemy sa odlisujú od sekvencnych systemov
u nemôzeme pouzit specifikaciu problemu prostrednúctvom mnoziny vstupných instanciú a fukncnej zavislosti medzi vstupom a pozadovanym výstupom
t nepostacuje dokaz konecnosti vypoctu a spravnosti vstupno-vystupneho vztahu
t nepostacuje vyjadrenie efektivity cez casovu (počet krokov od začiatku do ukončenia) a priestorovú zlozitost
ake vlastnosti požadujeme od súbežných procesov?
IB110 Podzim 2010
27
Alternatívne výpočtový modely^SúbeZnost ^ ^
Vlastnosti Živosti a bezpeCnosti
Vlastnosti, ktore pozadujeme od protokolov pre síbezne procesý (najcastejsie) spadaju do dvoch kategírií: bezpecnost a zivost.
t nikdý nenastanu „spatne" udalosti resp. vzdý sa stavaju len „dobre" udalosti
urcite „dobre" udalosti sa nakoniec stanu
abý sme ukazali, ze protokol porusuje vlastnost bezpecnosti, stací ukazat konkretnu postupnosl! akcií, ktore vedí k zakízanej udalosti
abý sme ukazali, ze protokol porusuje vlastnosl! zivosti, musíme ukazal! existenciu nekonecnej postupnosti akcií, ktore nevedu k pozadovanej dobrej udalosti
IB110 Podzim 2010
28
Alternatívne výpočtové modely^SúbeZnost ^ ^
Overovanie vlastností živosti a bezpečnosti
a mozu odhalit' čhybu, ale nemozu dokúzat platnosť pozadovanej vlastnosti; tečhniky sú jednodučhe
a matematičkú metóda, ktorú dokáže platnosť pozadovanej vlastnosti;
metoda overovania modelov (model checking)
naročne na implementačiu a samotne overenie vlastnosti;
pre niektore systemy je problem nerozhodnutemú
IB110 Podzim 2010
29
Alternatívne výpočtové modely ^Súbežnost ^ ^
Temporálna logika
jazyk pre popis vlastností súbežných systémov
formule logiky sa vyjadrujú o pravdivosti základných tvrdení v Case (v priebehu výpočtu)
zakladne konstrukcie: globalna platnost; (globally, G) a platnost; v budúcnosti (future, F)
príklady - protokol vzajomneho vylúcenia pre dva procesy Pi-je-v-(1.4)       F (Pi-je-v-(1.5)) G (-[Pi-je-v-(1.5) A P2-je-v-(1.5) ])
IB110 Podžim 2010
30
Alternatívne výpočtovú modelyKvantove počítanie ^ ^
Alternatívne výpočtove modely
Paraleližmus
Kvantove pocítanie Molekularne pocítan Nahodnostne algorit
IB110 Podzim 2010
31
Alternatívne výpočtový modelyKvantove počítanie ^ ^
Kvantove počítanie
zalozene na princípoch kvantovej mechaniký
teoretický model: zakladnou jednotkou reprezentície informacieje qubit, ktorý (zjednodusene) moze nadobídat ľuboboľní hodnotu z intervalu [0,1]
kvantove algoritmý
otazka konstrukcie kvantoveho pocítaca
IB110 Podzim 2010
32
AIternatívne výpočtový modeIy^MoIekuIárne počítanie ^ ^
AIternatívne vypoCtove modeIy
Hparalelizmus
HKvantove pocítanie ll Molekularne pocítanie HNahodnostne algoritmý
IB110 Podzim 2010
33
Alternatívne výpočtovú modely^Molekulárne počítanie ^ ^
Molekularne (DNA) poCítanie
■ DNA == retazce nad abededou A, C, T, G
■ vývoj organizmu == manipulacia s retazcacmi: kopírovanie, rozdeľovanie, spajanie
■ 1994: experiment, v ktorom pomocou manipulacie s molekulami bola výriesena instancia problemu Hamiltonovskeho cýklu velkosti 7; experiment predstavoval niekoľko dní laboratórnej prace
■ pozitívum: vel'ka miera paralelizmu
■ negatívum: velký objem biologickeho materialu potrebneho k rieseniu rozsiahlejsích instanci í
buducnost: ???
IB110 Podzim 2010
34
AIternatívne vypočtove modeIy^ Náhodnostne aIgoritmy ^ ^
Alternatívne výpočtove modelý
Paralelizmus
Kvantove počítanie Molekularne pocútanie Núahodnostnúe algoritmy
IB110 Podzim 2010
35
Alternatívne výpočtové modely    Náhodnostné algoritmy ^ ^
nahodnostný protokol pre večerajučičh filozofov
IB110 Podzim 2010
36
Alternatívne výpočtovú modely^ Núhodnostne algoritmy ^ ^
Porovnavanie reťazcov
Na pocítacoch A a B su ulozene databazý x a y; nech x a y su binírne retazce dlzký n. Úlohou je rozhodnít, ci x a y su zhodne. Zaujíma nas, kol'ko bitov si musia pocítace A a B výmenit, abý dokízali výriesit problíem rovnosti.
Dí sa dokazat, ze neexistuje deterministický komunikacný protokol, ktorý bý riesil problíem rovnosti a pritom si A a B výmenili nanajvíýs n - 1 bitov. T.j. protokol, v ktorom A posle celý retazec x pocítacu B je optimalný.
IB110 Podzim 2010
37
Alternatívne výpočtové modelyNáhodnostné algoritmy ^ ^
Porovnávanie reťazcov
Randomizovaný protokol pre problém rovnosti Vstup x = xiX2 ... xn, y = yiy2 ... y„ Krok 1 A vyberie náhodne prvočíslo p z intervalu [2, n2]. Krok 2 A vypočíta číslo s = x mod p a poSle čísla s, p počítaču B. Krok 3 B vypočíta číslo q = y mod p.
Ak n = 1016, tak zložitosť deterministického protokolu je 1016, zatiaf čo zložitost randomizovaného protokolu je 256.
Pravděpodobnost, že randomizovaný protokol vráti nesprávnu odopoved'
Ak q = s, tak B vráti odpoved' x = y. Ak q = s, tak B vríati odpoved x = y.
n
je < 0.36892 • 10-14.
IB110 Podzim 2010
38
Alternatívne výpočtovú modely» Núhodnostne algoritmy » »
Randomizovany Quicksort
Rand-Quicksort(A)
Vstup zoznam prvkov A
Krok 1  ak A ma jeden prvok, je utriedený
ak A ma viac prvkov, tak nahodne výber prvok x z A
Krok 2 výtvor zoznam A< obsahujuci prvký z A mensie nez x výtvor zoznam A> obsahujuci prvký z A väcsie nez x
Krok 3 výstup je Rand-Quicksort(A<), x, Rand-Quicksort(A>) ocakavana zlozitost algoritmu je O(N log N)
IB110 Podzim 2010
39
Alternatívne výpočtové modely^ Núhodnostné algoritmy ^ ^
Typy núhodnostnych algoritmov
o s ohranicenou pravdepodobnostou je odpoved' nespravna príklad: randomizovany protokol pre problem rovnosti
s odpoved' je vzdy spravna; ciel': ocakavanú zlozitost Las Vegas algoritmu pre problem je lepsia nez zlozitosl! (deterministickeho) algorimtu príklad: randomizovany Quicksort
IB110 Podžim 2010
40
Alternatívne vípočtove modely^ Níhodnostne algoritmy ^ ^
Nahodnostne zložitostne triedy
Pravdepodobnostný Turingov stroj
pracuje ako nedeterministický TS s tým rozdielom, ze nedeterministickí výber kroku výpoctu interpretujeme ako níhodnostní volbu
Trieda RP
obsahuje rozhodovacie problemý, pre ktore existuje polýnomialne casovo ohranicený pravdepodobnostný Turingov stroj s vlastnostou: ak odpoveďou pre vstup X je „Nie", tak s pravdepodobnostou 1 stroj da spraívnu odpoved
ak odpoved'ou je „Ano", tak stroj s pravdepodobnostou > 1/2 dí yes.
P C RP C NP
nahodnostne algoritmy nemôžu efektívne riesit problémy mimo NP; problémy z NP ale dokážu (často) riešit s väčšou efektivitou
IB110 Podzim 2010
41