1

USO DI CONCETTI PROBABILISTICI NEL PROGETTO ENELL’ANALISI DI ALGORITMI

- Analisi probabilistica di algoritmi deterministici: si assume unadistribuzione di probabilità delle istanze e si calcola il tempo diesecuzione atteso. In casi di distribuzioni semplici (es. nel sorting siassume che ogni permutazione sia equiprobabile) si può calcolare iltempo medio di esecuzione.- Progetto di algoritmi probabilistici: si assume che un algoritmo in

alcuni casi ‘getti una moneta’ (utilizzi un generatore di bit casuali) esi valuta quale è il risultato atteso e quale è il tempo di esecuzioneatteso.

2

ALGORITMIPROBABILISTICI

• Utili in molte circostanze per ottenere soluzioni efficienti e semplicidi problemi a vario livello di complessità.

• Possono commettere errori

• Lo studio della loro complessità richiede l’introduzione di classi dicomplessità probabilistiche.

3

L’utilizzazione della randomizzazione fa parte delle tecnichefondamentali di progetto di algoritmi già note.

ESEMPIHashing: nelle strutture dati (tabelle o alberi) per la gestione di dizionari,funzioni di randomizzazione delle chiavi (funzioni hash) consentono didistribuire in maniera uniforme le stringhe appartenenti ad undeterminato insieme (identificatori contenuti in un programma, chiavi diun database ecc.) e quindi ottenere con buona probabilità tempi diaccesso molto rapidi. naturalmente può accadere che due chiavi diverseabbiano lo stesso valoredella funzione hash dando luogo a conflitti chesi risolvono con vari metodi.

4

Quicksort: dato un vettore di n interi, l’algoritmo di ordinamentoquicksort ha un costo worst case O(n2) ma, nella sua versioneprobabilistica, in cui la scelta del perno è casuale, ha un costo attesoO(n log n) (algoritmo Random Quicksort).

5

L’algoritmo è del tipo ‘divide et impera’.Gli algoritmi di questo tipo hanno un comportamento efficiente seriescono a scomporre la soluzione del problema dato in due o piùsottoproblemi bilanciati, cioè di taglia sostanzialmente simile. Nella suaversione deterministica il quicksort non effettua una suddivisionebilanciata (o meglio può effettuarla solo scegliendo come perno ilmediano, ma questo passo è abbastanza costoso). Nella versionerandomizzata il fatto di scegliere il perno in modo casuale consenteinvece di avere con buona probabilità una suddivisione bilanciata e diottenere così un costo di esecuzione atteso molto migliore.

Il bilanciamento dei sottoproblemi ci da la relazione di ricorrenzaT(n) = 2 T(n/2) + cnche ha come soluzione T(n) = n log n.

6

Per ottenere una soluzione del tipo n log n non è necessario decomporreesattamente in due parti uguali il problema ma anche un rapporto 1/4 –3/4 tra i due sottoproblemi è accettabile. In questo caso la probabilità diestrarre un perno valido è molto più alta perché ci sono n/2 elementi chesono compresi tra l’elemento di posizione n/4 e quello di posizione 3n/4.

La relazione di ricorrenza diventa:T(n) = cn + T(n/4) + T(3n/4)Si verifica immediatamente che T(n) = O(n log n) soddisfa la relazione.

Una dimostrazione più formale si ottiene calcolando esattamente quale èil numero atteso di confronti che vengono effettuati dall’algoritmoRandom Quicksort.

7

Si noti che già questi due primi esempi mostrano che gli algoritmirandomizzati possono avere due comportamenti molto diversi:- nel caso dell’hashing abbiamo che una possibilità di errore

(unilaterale) se il valore della funzione hash di due chiavi è diversale chiavi sono sicuramente diverse ma se il valore è uguale le chiavipossono essere uguali o diverse (algoritmo sempre veloce e conbuona probabilità corretto, ma a volte scorretto – ALGORITMI‘MONTECARLO’);- nel caso del random quicksort la randomizzazione incide solo sul

costo dell’algoritmo ma la soluzione è comunque sempre corretta(algoritmo sempre corretto e con buona probabilità veloce, ma avolte lento – ALGORITMI ‘LAS VEGAS’).

8

PARADIGMI

- Randomizzazione dell’input. Per evitare le istanze più sfavorevoli unalgoritmo probabilistico può ‘rimescolare’ l’input in modo casuale epoi risolvere il problema con un procedimento più ‘semplice’. In moltiproblemi le istanze sfavorevoli sono molto rare e un riordinamentocasuale può raramente creare una istanza difficile.

- Abbondanza di testimoni. In molti problemi, una proprietà dell’input(grafo, stringa, numero intero) è attestata da ‘testimoni’. Spessocercarli deterministicamente può costare molto tempo ma se ce nesono molti può essere facile trovarli in modo probabilistico.

- Campionamento casuale. Se scelto correttamente un campione casualepuò essere rappresentativo di una intera popolazione (sondaggi).

9

- Riduzione dello spazio delle istanze. In molti problemi abbiamo a chefare con un ‘piccolo’ insieme di dati appartenenti a un ‘grande’universo. In questi casi possiamo usare la randomizzazione permappare i dati su un piccolo universo. Esempi:

- Hashing: citato precedentemente

- Fingerprinting: date due stringhe x, y di n bit (es.: n=220) perdecidere se x=y in modo deterministico dobbiamo controllarecarattere per carattere mentre in modo probabilistico possiamoconfrontare sottostringhe molto più corte.

10

Al fine di illustrare alcuni algoritmi probabilistici introduciamol’istruzione random (n, m) che restituisce come valoreun numero intero a caso tra n ed m, con probabilità uniforme 1/(m-n+1).

Nota bene. Il fatto che l’istruzione ‘random’ fornisca un numero a casotra n ed m con probabilità uniforme è una assunzione teorica che ciconsente di analizzare il comportamento di un algoritmo probabilistico.In pratica l’istruzione farà ricorso a un generatore di numeripseudocasuali. Anche una moneta avrà sempre una leggerapolarizzazione che non garantisce che la probabilità di avere testa ocroce sia esattamente 1/2. La possibilità di disporre in pratica di sorgentirealmente casuali è uno dei problemi fondamentali della teoria deglialgoritmi probabilistici.

11

TEST DI PRIMALITA’

Il ‘piccolo’ teorema di Fermat afferma che per ogni primo ped ogni a ∈ [2,…, p-1]: ap-1 mod p = 1.

In particolare tale risultato vale per a = 2. Ciò consente di definire ilseguente algoritmo per il test di primalità

ALGORITMO PSEUDOPRIMISe 2n-1 mod n ≠ 1 allora restituisci ‘n è composto’

altrimenti restituisci ‘n è primo’

Questo algoritmo presenta una certa probabilità di errore perché esistononumeri composti n che soddisfano l’equazione 2n-1 mod n = 1 e quindipossono essere dichiarati erroneamente ‘primi’.

12

Esistono anche numeri composti n (numeri di Carmichael) tali chel’equazione an-1 mod n = 1 è soddisfatta per ogni a ∈ [2,…, n-1].E’ necessario un test più raffinato.

13

TEST DI COMPOSTEZZA DI RABIN E MILLER

Un intero a∈[2,…, n-1] è un testimone della compostezza di n se:1) an-1 mod n ≠ 1,

oppure se:2) esiste un intero t ≥ 1 tale che n-1 = m 2t (la rappresentazione

binaria di n-1 è uguale alla rappresentazione binaria del numerodispari m seguito da t zeri) e il MCD tra am – 1 ed n appartiene a[2,…, n-1].

14

Se a testimonia che n è composto, n è effettivamente composto.

Infatti se vale la 1, n non soddisfa il teorema di Fermat e se vale la 2, ndeve ammettere un divisore proprio.

NOTA BENE. Utilizzando risultati della teoria dei numeri si puòdimostrare che se n è composto esistono in [2, …, n-1] almeno 3(n-1)/4numeri interi che testimoniano la sua ‘compostezza’.

15

ALGORITMO RANDOM TEST DI COMPOSTEZZA

input: na ← random (2, n-1)se a testimonia la compostezza di n

allora accetta, altrimenti rifiuta

L’algoritmo ha un costo di esecuzione polinomiale perché la verifica chea testimonia la compostezza può essere fatta in tempo polinomiale.Poiché, come si è detto, se n è composto esistono 3(n – 1)/4 testimoni tra2 ed n-1, abbiamo che la probabilità che se n è composto non vengaestratto un numero che non è un testimone di compostezza è al più 1/4.Quindi se n composto → l’algoritmo accetta con probabilità ≥ 3/4

se n primo → l’algoritmo rifiuta

16

Per migliorare l’affidabilità dell’algoritmo possiamo ripeternel’applicazione estraendo ogni volta in modo indipendente dalleestrazioni precedenti un valore a. In tal modo, in k passi la probabilità dierrore si riduce ad 1/4k e diventa rapidamente inferire alla possibilità chesi verifichi un errore a livello hardware.

Si noti che l’algoritmo può commettere errori ‘da un solo lato’, infatti• se n è primo viene sicuramente rifiutato (rifiutato con probabilità 1)• se n è composto viene accettato con probabilità 3/4 e rifiutato con

probabilità 1/4.

17

Un algoritmo probabilistico che può errare nell’accettazione e/o nelrifiuto viene detto un algoritmo di tipo ‘Monte Carlo’.

In generale un algoritmo probabilistico può commettere errori- unilaterali- bilaterali.

Un algoritmo di tipo ‘Las Vegas’ è invece un algoritmo probabilisticoche, se risponde, dà risposte corrette ma a volte potrebbe non rispondere(o potrebbe rispondere ma solo dopo un numero sufficiente di iterazionie quindi impiegando un tempo eccessivamente lungo).

18

Si noti che gli algoritmi probabilistici trovano le loro più valideapplicazioni nella risoluzione di problemi di costo polinomiale o diproblemi che sono in NP-P ma non NP-completi. Infatti si puòdimostrare che se per un problema NP-completo potessimo trovare unalgoritmo polinomiale la cui probabilità di errore possa essere resaarbitrariamente piccola, allora esisterebbero algoritmi di tale tipo perqualunque problema in NP, un fatto che si ritiene inverosimile.

19

PRODOTTO DI MATRICI (Algoritmo di Freivald)

Il problema consiste nel determinare, date tre matrici, A, B, C se A×B =C. Nessun algoritmo è in grado di risolvere questo problema in mododeterministico in un tempo inferiore a O(n2.4), il miglior tempo noto peril prodotto di matrici. Il seguente algoritmo risolve il problema in tempoO(n2) con un errore ≤ 1/2.

ALGORITMO RANDOM PRODOTTO DI MATRICIinput: A, B, Cper i che va da 1 a n ripeti x[i] ← random (0, 1)se A(Bx) = Cx allora accetta,

altrimenti rifiuta.

20

DIMOSTRAZIONE

Chiaramente se l’algoritmo rifiuta esso si comporta correttamentementre quando accetta potrebbe errare, infatti potrebbe accettare anchese A×B ≠ C. Però possiamo dimostrare che ciò accade al più per metàdei 2n vettori x in (0,1)n, cioè almeno 2n-1 vettori testimonianocorrettamente che A×B ≠ C (in altre parole A (B x)) ≠ C x).

Poiché se A×B ≠ C la matrice D = A×B – C non è nulla, è sufficientemostrare che per 2n-1 vettori x il prodotto Dx = δ = (δ1, δ2, ... δn)non è nullo. Supponiamo che la riga di in D non sia nulla e chedis1, … disk siano i suoi elementi non nulli (k≥1).

21

Dobbiamo dimostrare che δi = Σj dij xj = Σh dish xsh ≠ 0per almeno 2n-1 vettori x.

Infatti se fosse δi = 0 avremmo

xs1 = - 1/ dis1 Σ dish xsh per 2 ≤ h ≤ n

e quindi il valore xs1 sarebbe fissato univocamente e resterebbero liberisolo (al più) i restanti n-1 elementi. In altre parole, se x annulla una riganon nulla di D, almeno una delle sue componenti resta fissata e quindinon ci possono essere più di 2n-1 vettori che annullano una riga nonnulla.QED

22

TEST DI NULLITA’ DI UN POLINOMIO

Il problema consiste nel decidere se un polinomio Q nelle variabili x1,..., xn, fornito in una forma algebrica generale, è identicamente nullo.

NOTA BENE. Se il polinomio venisse fornito come somma di monomila verifica sarebbe banale ma se viene fornito con una espressionealgebrica generale gli algoritmi di semplificazione necessari per metterlosotto forma di somma di monomi sarebbero di costo troppo elevato.

23

Supponiamo che g(Q) sia il grado del polinomio (o un upper bound diesso). Si può dimostrare che se Q NON è identicamente nullo, allora,per ogni costante c > 1, e per ogni insieme I di interi con |I| ≥ cg(Q), ilnumero di elementi y=(y1, ..., yn) ∈ In per cui Q(y1, ..., yn) = 0 è al più|I|n /c. A partire da questo risultato è possibile definire il seguentealgoritmo probabilistico in cui si assume I = {1,2, ..., 2g(Q)}.

ALGORITMO RANDOM TEST POLINOMIO NULLO

input: Qper i che va da 1 a n ripeti

y[i] ← random (1, 2g(Q))se Q(y[1], ..., y[n]) ≠ 0 allora rifiuta, altrimenti accetta.

24

DIMOSTRAZIONEAvendo assunto c=2 abbiamo che al più 1/2 dei vettori y=(y1, ..., yn)generati a caso potrà dare Q(y) = 0. Quindi- se Q è nullo viene sicuramente accettato- se Q non è nullo abbiamo una probabilità 1/2 che sia rifiutato e una

probabilità 1/2 che sia accettato.Anche in questo caso abbiamo un errore unilaterale. QED

Un risultato strettamente legato al precedente consente di realizzare unalgoritmo probabilistico per determinare se due polinomi sono distinti.Sia dato un campo F di cardinalità q.Due diversi polinomi Q1 e Q2 con k variabili e di grado massimo gpossono concordare al più su gqk-1 elementi di Fk.

25

CLASSI DI COMPLESSITA’PROBABILISTICHE

Per formalizzare le computazioni probabilistiche e studiare le relativeclassi di complessità dobbiamo innanzitutto introdurre le macchine diTuring probabilistiche.

Per far ciò partiamo da macchine di Turing non deterministiche per lequali facciamo le seguenti assunzioni semplificatrici.- Il grado di non determinismo è 2.- Ogni passo è non deterministico.- Ogni computazione si svolge in tempo polinomiale.- Tutte le computazioni hanno la stessa durata.

26

Se ora interpretiamo i rami di una computazione non deterministicacome risultati di una sequenza di t scelte casuali indipendenti tra duealternative (scelte ogni volta con probabilità 1/2) abbiamo che ognicomputazione ha la probabilità 1/2t di realizzarsi.

Assumendo che ogni computazione abbia tre possibili esiti: 1, 0, ?,abbiamo che il risultato di una computazione M(x) con input x è unavariabile casuale e quindi siamo interessati a valutareProb {M(x) = z} dove z ∈ (1,0,?).

Definiamo:α(M, x): Prob {M(x) = 1}β(M, x): Prob {M(x) = 0}

27

MACCHINE DI TURING PP(PROBABILISTIC POLYNOMIAL-TIME) CLASSE PPUna macchina di Turing probabilistica M è di tipo PP se:- M ha due stati finali, uno di accettazione ed uno di rifiuto,- M accetta x se α(M, x) > 1/2 (x∈L M accetta con Prob>1/2)- M rifiuta x se β(M, x) ≥ 1/2 (x∉L M accetta con Prob≤1/2)

ESEMPIOSupponiamo di voler decidere se, data una formula Booleana w, w èsoddisfatta da più della metà delle assegnazioni di valori di verità.Chiaramente tale problema ammette una macchina di tipo PP che lorisolve; il problema è dunque nella classe PP.

28

NOTA BENE Le macchine PP possono commettere errore bilaterale.

La classe PP non è molto utilizzata perché per ridurre significativamentela probabilità di errore può essere necessario un numero esponenziale diiterazioni (si pensi ad esempio al caso in cui l’errore è 1/2 - 1/2p(n) ).

29

MACCHINE DI TURING BPP (BOUNDED PP) CLASSE BPPUna macchina di Turing probabilistica M è di tipo BPP se esiste unacostante ε ∈ (0, 1/2) (estremi esclusi) tale che:- M ha due stati finali, uno di accettazione ed uno di rifiuto,- M accetta x se α(M, x) >1/2+ε (x∈L M accetta con Prob>1/2+ε)- M rifiuta x se β(M, x) >1/2+ε (x∉L M rifiuta con Prob>1/2+ε)- per ogni x o α(M, x) >1/2+ε o β(M, x) >1/2+ε.

Nel caso delle macchine BPP un numero polinomiale di iterazioniconsente di rendere l’errore piccolo a piacere. Ciò è possibile qualunquesia la costante ε, purché diversa da 0. Anche le macchine BPPcommettono errore bilaterale.

30

TEOREMA Sia M una macchina di tipo BPP e sia q un polinomio.Allora esiste una macchina di Turing probabilistica M’ tale che, per ognix, con |x|=n,x∈L M accetta con Prob α(M’, x) >1 – 1/2q(n)

x∉L M rifiuta con Prob β(M’, x) >1 – 1/2q(n)

Alla luce del precedente teorema una definizione equivalente dellaclasse BPP è la seguente:

x∈L M accetta con Prob>3/4x∉L M accetta con Prob<1/4

NOTA BENE Le macchine BPP possono commettere errore bilaterale.

31

MACCHINE DI TURING RP(RANDOM P) CLASSE RPUna macchina di Turing probabilistica M è di tipo RP se:- M ha due stati finali, uno di accettazione ed uno di rifiuto,- M accetta x se α(M, x) >1/2 (x∈L M accetta con Prob>1/2)- M rifiuta x se β(M, x) =1 (x∉L M rifiuta con Prob=1)- per ogni x o α(M, x) >1/2 o β(M, x) =1.

Le macchine di tipo RP commettono errore unilaterale. Anche nellemacchine di tipo RP l’errore può essere reso piccolo a piacere.

ESEMPIL’insieme dei numeri composti appartiene a RP. I problemidell’uguaglianza di matrici (AB=C) e del polinomio nullo appartengonoa co-RP

32

NOTA BENE Nella definizione dell’accettazione di una macchina RPnon abbiamo richiesto (come nel caso BPP) che fosse α(M, x) >1/2 + ε.Ciò è dovuto al fatto che si può dimostrare che RP ⊆ BPP.

33

MACCHINE DI TURING ZPP (ZERO ERROR) CLASSE ZPP

Una macchina di Turing probabilistica M è di tipo ZPP se:- M ha tre stati finali, uno di accettazione, uno di rifiuto, ed uno di

incertezza- M accetta x se α(M, x) >1/2 e β(M, x) =0- M rifiuta x se β(M, x) > 1/2 e α(M, x) = 0- per ogni x o α(M, x) >1/2 e β(M, x) =0

o β(M, x) >1/2 e α(M, x) =0.

Le macchine di tipo ZPP corrispondono agli algoritmi di tipo LasVegas: una macchina di tipo ZPP non commette errori. Un algoritmo ditipo Las Vegas per il problema della primalità si può trovare nel testo diBovet e Crescenzi, Teoria della complessità computazionale.

34

CLASSI DI COMPLESSITA’ PROBABILISTICHE

TEOREMA Le classi PP, BPP, ZPP sono chiuse rispetto alcomplemento.

DIMOSTRAZIONELe definizioni delle classi presentano simmetria rispetto ad accettazionee rifiuto.QED

TEOREMA Le classi BPP, RP e ZPP sono chiuse rispetto ad unione edintersezione.DIMOSTRAZIONEDimostriamo che BPP è chiuso rispetto all’unione (analogo per RP eZPP).

35

Siano L1 ed L2 due linguaggi in BPP. In base alle proprietà viste per lemacchine di tipo BPP possiamo asserire che esistono due macchineM1ed M2 tali che, per i=1,2, x∈Li implica che α(Mi, x) > 1 – εx∉Li implica che β(Mi, x) > 1 – ε ove ε ∈ (0, 1/2).Consideriamo dunque una macchina M di tipo BPP che simula una dopol’altra M1 ed M2 e accetta se e solo se una delle due macchine haaccettato.Se x ∈ L1 ∪ L2 allora α(M, x) > 1 – ε,se x ∉ L1 ∪ L2 allora β(M, x) > (1 – ε)2.

36

Se garantiamo che ε sia tale che (1 – ε)2>1/2 (ad esempio ε=1/4)e definiamo ε’= 1 – (1 – ε)2 abbiamo chese x ∈ L1 ∪ L2 allora α(M, x) > 1 – ε > (1 – ε)2 = 1 – ε’se x ∉ L1 ∪ L2 allora β(M, x) > 1 – ε’

Quindi M accetta L1 ∪ L2 e quindi L1 ∪ L2 ∈ BPP. QED

37

Tra le classi probabilistiche valgono le seguenti relazioni di inclusione.

TEOREMA P ⊆ ZPP

DIMOSTRAZIONESe L è in P allora poniamo tutte le computazioni della macchinaprobabilistica uguali alla computazione deterministica che decide L edotteniamo chese x∈L allora α(M, x) =1se x∉L allora β(M, x) =1.QED

38

TEOREMA ZPP = RP ∩ co-RP

DIMOSTRAZIONEMostriamo innanzitutto che ZPP ⊆ RP e che ZPP ⊆ co-RP, e quindiZPP ⊆ RP ∩ co-RP.Per mostrare che ZPP ⊆ RP è sufficiente trasformare una macchina ditipo ZPP in una macchina di tipo RP e a tal fine possiamo trasformareuna computazione che termina in uno stato di incertezza in unacomputazione rifiutante.Per mostrare che ZPP ⊆ co-RP è sufficiente ricordare che ZPP è chiusorispetto alla complementazione.Per mostrare che RP ∩ co-RP⊆ ZPP consideriamo un linguaggio L inRP ∩ co-RP.Allora esistono due macchine di tipo RP M1 ed M2 che accettanorispettivamente L ed il suo complemento.

39

Possiamo scrivere per il linguaggio L il seguente algoritmo di tipo ZPP.

input: xsimula M1(x)se M1 accetta allora accettasimula M2(x)se M2 accetta allora rifiutaaltrimenti termina nello stato di incertezza.

Poiché M1 ed M2 sono macchine di tipo RP allora è facile verificare chese x∈L allora α(M, x) > 1/2 e β(M, x) = 0se x∉L allora α(M, x) = 0 e β(M, x) > 1/2.QED

40

TEOREMA RP ⊆ NP; co-RP ⊆ co-NP

DIMOSTRAZIONEConsideriamo la macchina di Turing di tipo RP come una macchina nondeterministica. Se L∈RP allora abbiamo che:- se x∈L allora α(M, x) > 1/2 e quindi esiste almeno una computazione

accettante- se x∉L allora β(M, x) = 1 e quindi tutte le computazioni rifiutano.QED

41

TEOREMA RP ∪ co-RP ⊆ BPP

DIMOSTRAZIONE

Dimostriamo che RP ⊆ BPP. Poiché BPP è chiuso rispetto allacomplementazione, vale anche co-RP ⊆ BPP e quindi vale l’enunciatodel teorema.Sia M una macchina di tipo RP; se M accetta x allora β(M, x) < 1/2.Definiamo una macchina BPP M’ che simula due volte M e accetta x sealmeno una delle due computazioni della M accetta.Quindi se M’ accetta α(M’, x) > 1 - 1/4; assumendo ε = 1/4 abbiamoα(M’, x) > 1/2 + ε. Se M’ rifiuta β(M’, x) = 1 > 1/2 + ε. QED

42

TEOREMA NP ∪ co-NP ⊆ PP

DIMOSTRAZIONE Dimostriamo che NP ⊆ PP. Poiché PP è chiusorispetto alla complementazione è chiaro che abbiamo anche co-NP ⊆PP. Sia data una macchina non deterministica M che accetta unlinguaggio L ∈ NPRealizziamo una semplice macchina probabilistica M’ che opera nelseguente modo: su input x al primo passo si dirama in due sottoalberi.Quello di sinistra corrisponde alla computazione non deterministicadella macchina M (di profondità p(n)) e quello di destra è un alberocompleto di computazioni deterministiche di profondità p(n) cheaccettano sempre. Se x∈L allora almeno la metà più uno dellecomputazioni accetta e quindi x viene accettata con probabilitàα(M,x)>1/2.

43

Altrimenti esattamente la metà delle computazioni accettano e quindi lastringa viene rifiutata con probabilità β(M,x)=1/2. QED

TEOREMA BPP ⊆ PP

Questo risultato deriva banalmente dalla definizione dei due tipi dimacchina.

44

TEOREMA PP ⊆ PSPACE

DIMOSTRAZIONE Se un linguaggio L è deciso da una macchinaprobabilistica di tipo PP in tempo p(n) possiamo mostrare che L puòessere deciso dal seguente algoritmo deterministico che usa spaziopolinomiale:For i= 1 to 2p(n) doif l’iesima computazione deterministica accetta then cont = cont + 1endif cont > 2(p(n) – 1) then accetta else rifiuta

45

Problemi aperti:

- RP = co-RP? (conseguenza: RP ⊆ NP∩co-NP)- BPP ⊆ NP?