Esercizio - Dimostrazione che ZPP è uguale a RP intersecato co-RP

Testo (domanda da orale). Si ricordano: RP = linguaggi con un algoritmo polinomiale che, se $x\in L$, risponde SI con probabilità $\ge1/2$ e, se $x\notin L$, risponde NO sempre; co-RP = complementi; ZPP = linguaggi con un algoritmo Las Vegas di tempo atteso polinomiale.

1. Dimostrare che $\text{ZPP}\subseteq\text{RP}\cap\text{co-RP}$.
2. Dimostrare che $\text{RP}\cap\text{co-RP}\subseteq\text{ZPP}$ e calcolare il numero atteso di giri.
3. Se gli algoritmi $A$ (RP) e $B$ (co-RP) hanno probabilità di riuscita $0{,}3$ invece di $1/2$, quanti giri servono in media?

Teoria: Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione → (classi e teorema ZPP).

Soluzione

Punto 1. Sia $V$ un Las Vegas per $L$ con $E[T]\le q(n)$, $q$ polinomio. Per la disuguaglianza di Markov (Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →) $\Pr[T\ge2q(n)]\le\frac{E[T]}{2q(n)}\le\frac12$.

• Algoritmo $A$: si esegue $V$ per al più $2q(n)$ passi. Se finisce, si risponde come $V$ (sempre corretto). Se non finisce, si risponde NO.
• Se $x\notin L$: $V$, quando finisce, dice NO; e il time-out dà NO. Quindi $A$ non dice mai SI: errore $0$.
• Se $x\in L$: $A$ dice SI se $V$ finisce in tempo, probabilità $\ge1/2$. Quindi $A$ è un algoritmo RP, polinomiale perché si ferma a $2q(n)$ passi.
• Algoritmo $B$: uguale, ma al time-out risponde SI. Con lo stesso ragionamento $B$ non dice mai NO se $x\in L$ e dice NO con probabilità $\ge1/2$ se $x\notin L$: è co-RP.

Punto 2. Siano $A$ RP e $B$ co-RP per $L$. L'algoritmo Las Vegas esegue giri:

1. si esegue $A(x)$; se risponde SI, si risponde SI (certo, perché $A$ non ha falsi SI);
2. si esegue $B(x)$; se risponde NO, si risponde NO (certo, perché $B$ non ha falsi NO);
3. altrimenti si ricomincia da 1 con nuovi bit casuali.

La risposta è sempre corretta. In un giro: se $x\in L$ allora $A$ dice SI con probabilità $\ge1/2$; se $x\notin L$ allora $B$ dice NO con probabilità $\ge1/2$. Quindi ogni giro termina con probabilità $\ge1/2$, i giri sono indipendenti, il loro numero è geometrico e in media $\le2$. Il tempo atteso è $\le2$ volte il costo di un giro, polinomiale.

Punto 3. Se la riuscita per giro è $q=0{,}3$ (indipendentemente dal caso, $x\in L$ o $x\notin L$), il numero di giri è geometrico di parametro $0{,}3$: in media $1/0{,}3=3{,}33$ giri. Una simulazione con $2\cdot10^5$ giri indipendenti dà $3{,}34$; per $q=1/2$ dà $2{,}00$.

Risultato: $\text{ZPP}=\text{RP}\cap\text{co-RP}$; giri attesi $\le2$ (e $10/3$ per $q=0{,}3$).

import random
def giri(q):
    n = 0
    while True:
        n += 1
        if random.random() < q: return n
for q in (0.5, 0.3):
    print(q, sum(giri(q) for _ in range(200000)) / 200000, 1 / q)      # 2.00, 3.34 (attesi 2 e 3.33)