Esercizio - Conteggio delle soluzioni di una formula DNF con l'algoritmo di Karp e Luby

Teoria: Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMCMonte Carlo stima una grandezza come media di campioni casuali: errore tipico σ/√N, numero di campioni N ≥ ln(2/δ)/(2ε²) per Hoeffding (probabilità), N ≥ 3 ln(2/δ)/(pε²) per Chernoff (errore relativo). Stima di π con p=π/4; integrali come media di g(U); eventi rari con campionamento per importanza (pesi φ/q); conteggio DNF con Karp-Luby in tempo polinomiale perché P(Y=1) ≥ 1/m. Generazione: trasformazione inversa X=F^{-1}(U) e accettazione-rifiuto (f ≤ M g, efficienza 1/M). MCMC: Metropolis-Hastings costruisce una catena con stazionaria π (nota a meno di costante) imponendo il bilancio dettagliato con probabilità di accettazione min(1, π(y)Q(y,x)/(π(x)Q(x,y))).Metodi Monte Carlo - stima, generazione di variabili aleatorie e MCMC →.

Testo. Sia $\varphi=T_1\vee T_2\vee T_3\vee T_4$ una DNF su $x_1,\dots,x_5$ con $$T_1=x_1\wedge x_2\wedge\neg x_3,\quad T_2=x_2\wedge x_4,\quad T_3=\neg x_1\wedge x_5,\quad T_4=x_3\wedge x_5.$$

1. Calcolare $|S_i|$ per ogni termine e $\sum_i|S_i|$.
2. Contare con precisione $|U|=|\bigcup_iS_i|$ (le assegnazioni che soddisfano $\varphi$), elencando le molteplicità.
3. Calcolare $E[Y]$ dell'algoritmo di Karp-Luby e la probabilità $P(Y=1\mid i)$ per ciascun termine.
4. Eseguire a mano un campione con $i=2$ e $x=(0,1,1,1,0)$ (l'assegnazione ottenuta fissando $x_2=x_4=1$ nel termine $T_2$ e scegliendo a caso le altre variabili). Quanto vale $Y$?
5. Quanti campioni per un errore relativo $\le2\%$ con probabilità $\ge99\%$? Quanto vale la stima con $2\cdot10^5$ campioni?
6. Confrontare con il campionamento ingenuo.

Soluzione

1. Un termine con $k$ letterali fissa $k$ variabili e lascia libere $5-k$: $|S_i|=2^{5-k_i}$. $T_1$ ha $3$ letterali: $|S_1|=4$; $T_2$ ha $2$: $|S_2|=8$; $T_3$ ha $2$: $|S_3|=8$; $T_4$ ha $2$: $|S_4|=8$. Somma: $\boxed{28}$.

2. Elenchiamo le assegnazioni $x_1x_2x_3x_4x_5$ di ciascun $S_i$:

• $S_1$ ($x_1=1,x_2=1,x_3=0$): $11000,\,11001,\,11010,\,11011$;
• $S_2$ ($x_2=1,x_4=1$): $01010,\,01011,\,01110,\,01111,\,11010,\,11011,\,11110,\,11111$;
• $S_3$ ($x_1=0,x_5=1$): $00001,\,00011,\,00101,\,00111,\,01001,\,01011,\,01101,\,01111$;
• $S_4$ ($x_3=1,x_5=1$): $00101,\,00111,\,01101,\,01111,\,10101,\,10111,\,11101,\,11111$.

Le assegnazioni comuni a più insiemi sono: $11010,\,11011\in S_1\cap S_2$; $01011\in S_2\cap S_3$; $00101,\,00111,\,01101\in S_3\cap S_4$; $01111\in S_2\cap S_3\cap S_4$; $11111\in S_2\cap S_4$. Per inclusione-esclusione, $|U|=28-(\text{ripetizioni})$: le assegnazioni contate più volte sono $11010$ ($2$), $11011$ ($2$), $01011$ ($2$), $00101$ ($2$), $00111$ ($2$), $01101$ ($2$), $01111$ ($3$), $11111$ ($2$), che producono $1+1+1+1+1+1+2+1=9$ ripetizioni in eccesso. Quindi $|U|=28-9=\boxed{19}$ (verificato con l'enumerazione di tutte le $32$ assegnazioni).

3. La coppia $(i,x)$ è uniforme sulle $28$ coppie con $x\in S_i$. Ogni $x\in U$ ha una sola coppia canonica (indice minimo). Quindi $E[Y]=\dfrac{19}{28}=0{,}6786$. Per ogni termine, $P(Y=1\mid i)=\dfrac{\#\{x\in S_i:\text{ nessun }T_j,\ j<i,\text{ soddisfatto}\}}{|S_i|}$: contando, le coppie canoniche sono $4,\,6,\,6,\,3$ (somma $19$), cioè $P(Y=1\mid i)=\dfrac44=1$, $\dfrac68=0{,}75$, $\dfrac68=0{,}75$, $\dfrac38=0{,}375$. Controllo: $\dfrac{4\cdot1+8\cdot0{,}75+8\cdot0{,}75+8\cdot0{,}375}{28}=\dfrac{4+6+6+3}{28}=\dfrac{19}{28}$ ✓. In generale $E[Y]\ge\tfrac1m=0{,}25$; qui è molto più alto.

4. Il termine scelto è $T_2$, e $x=(0,1,1,1,0)=01110\in S_2$ ✓. Quali termini soddisfa $x=01110$? $T_1$: richiede $x_1=1$, no. $T_2$: $x_2=x_4=1$ ✓. $T_3$: richiede $x_1=0$ e $x_5=1$, ma $x_5=0$, no. $T_4$: richiede $x_5=1$, no. Il più piccolo indice soddisfatto è $2=i$, quindi $\boxed{Y=1}$. (Con $x=11010$, sempre in $S_2$, sarebbe stato soddisfatto anche $T_1$ e quindi $Y=0$: $x$ viene contato dalla coppia $(1,11010)$.)

5. Con $m=4$, $\varepsilon=0{,}02$, $\delta=0{,}01$: $N\ge\dfrac{3m\ln(2/\delta)}{\varepsilon^2}=\dfrac{3\cdot4\cdot\ln200}{0{,}0004}=\boxed{158\,950}$ campioni (la garanzia usa solo $E[Y]\ge\tfrac1m$; il limite effettivo con $E[Y]=0{,}68$ sarebbe più basso). Con $2\cdot10^5$ campioni: $\bar Y=0{,}6788$ e la stima $28\cdot0{,}6788=19{,}005\approx19$ ✓.

6. Il campionamento ingenuo estrae un'assegnazione uniforme e controlla se soddisfa $\varphi$: ha probabilità di successo $\tfrac{19}{32}=0{,}594$, comparabile. Il vantaggio di Karp-Luby si vede quando $|U|/2^n$ è minuscolo: con $n=40$ e tre termini di $20$ letterali la frazione è $\le2{,}9\cdot10^{-6}$ e il metodo ingenuo richiederebbe $\approx10^6$ campioni per vedere un solo successo, mentre Karp-Luby ha sempre $E[Y]\ge\tfrac13$.

Codice di verifica

import itertools
import numpy as np
from math import log

n = 5
terms = [((0, 1), (1, 1), (2, 0)), ((1, 1), (3, 1)), ((0, 0), (4, 1)), ((2, 1), (4, 1))]   # (variabile, valore)
sat = lambda t, x: all(x[v] == s for v, s in t)
tutte = list(itertools.product((0, 1), repeat=n))
U = [x for x in tutte if any(sat(t, x) for t in terms)]
sizes = [2**(n - len(t)) for t in terms]
print("|S_i| =", sizes, " somma =", sum(sizes), " |U| =", len(U), " E[Y] =", len(U) / sum(sizes))
canon = [sum(1 for x in tutte if sat(t, x) and min(j for j, u in enumerate(terms) if sat(u, x)) == i)
         for i, t in enumerate(terms)]
print("coppie canoniche:", canon, [c / s for c, s in zip(canon, sizes)])

rng = np.random.default_rng(5)
N, hit, tot = 200_000, 0, sum(sizes)
for _ in range(N):
    i = rng.choice(len(terms), p=[s / tot for s in sizes])
    x = [int(rng.integers(0, 2)) for _ in range(n)]
    for v, s in terms[i]: x[v] = s
    hit += min(j for j, t in enumerate(terms) if sat(t, x)) == i
print("stima:", tot * hit / N, " N richiesto:", 3 * len(terms) * log(2 / 0.01) / 0.02**2)