Esercizio - Algoritmo randomizzato per 2-SAT eseguito su un'istanza con quattro variabili

Teoria: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafiPasseggiata sulla retta con barriere (rovina del giocatore): da i con N come traguardo, P(vittoria)=i/N e durata attesa i(N-i) se il gioco è equo; con p diverso da 1/2, P=(1-r^i)/(1-r^N), r=q/p. Il 2-SAT si risolve con una passeggiata randomizzata (flip di una variabile di una clausola violata): E[T] ≤ n^2 passi, quindi 2n^2 passi bastano con errore ≤ 1/2 (3-SAT: deriva contraria, esponenziale). Sul grafo la passeggiata ha π_v=d(v)/2m, tempo di ritorno 2m/d(v), tempo di copertura < 4m(n-1), da cui la connettività s-t in spazio logaritmico; PageRank è la stazionaria di una passeggiata con teletrasporto.Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi →.

Testo. Si considera la formula 2-CNF su $x_1,x_2,x_3,x_4$ $$\varphi=(\neg x_1\vee\neg x_2)\wedge(\neg x_1\vee x_2)\wedge(x_1\vee\neg x_2)\wedge(x_1\vee\neg x_3)\wedge(x_1\vee\neg x_4).$$

1. Trovare tutte le assegnazioni soddisfacenti.
2. Eseguire a mano l'algoritmo (passeggiata) da $(1,1,1,1)$, scegliendo come clausola violata la prima nell'ordine di scrittura, con la sequenza di scelte casuali $x_1,x_2,x_3,x_4$.
3. Il numero di passi atteso dipende dalla distanza $j$ dalla soluzione. Calcolare il valore esatto $E_j$ per ogni assegnazione di partenza (con la regola "prima clausola violata, variabile a caso tra le due") e confrontarlo con il limite $2jn-j^2$.
4. Calcolare la probabilità di non trovare la soluzione entro $2n^2=32$ passi partendo da un'assegnazione scelta uniformemente, e confrontarla con il limite $\tfrac12$ di Markov.
5. Cosa cambia scegliendo la clausola violata a caso invece che la prima?

Soluzione

1. Le prime due clausole insieme equivalgono a $\neg x_1$: se $x_1=1$ servirebbero $x_2=0$ (prima clausola) e $x_2=1$ (seconda), impossibile; quindi $x_1=0$. Con $x_1=0$ la terza clausola impone $\neg x_2$, la quarta $\neg x_3$, la quinta $\neg x_4$. L'unica soluzione è $S=(0,0,0,0)$.

2. La distanza da $S$ è il numero di variabili uguali a $1$.

Quattro passi, tutti nella direzione giusta: distanza $4\to3\to2\to1\to0$. Ogni passo ha avuto probabilità $\tfrac12$ di essere questo, quindi la sequenza ha probabilità $\bigl(\tfrac12\bigr)^4=\tfrac1{16}$ dato lo stato iniziale.

3. Sia $E(x)$ il numero atteso di passi da $x$ ($E(S)=0$). Per ogni $x\ne S$, $E(x)=1+\tfrac12E(x')+\tfrac12E(x'')$, dove $x',x''$ sono ottenute cambiando le due variabili della prima clausola violata. Il sistema ha $15$ incognite (una per assegnazione diversa da $S$); la soluzione (frazioni esatte con sympy, controllata con il codice sotto) per ogni assegnazione scritta come $x_1x_2x_3x_4$ è: $0001\!:5$, $0010\!:5$, $0100\!:3$, $1000\!:3$, $0011\!:10$, $0101\!:8$, $0110\!:8$, $1100\!:4$, $1001\!:8$, $1010\!:8$, $0111\!:13$, $1011\!:13$, $1101\!:9$, $1110\!:9$, $1111\!:14$. Il massimo per ogni distanza $j=1,2,3,4$ vale $5,\ 10,\ 13,\ 14$, sotto i limiti $2jn-j^2=7,\ 12,\ 15,\ 16$ e sotto $n^2=16$. Con partenza uniforme sulle $16$ assegnazioni la media è $\tfrac{0+3+3+5+5+10+8+8+4+8+8+13+13+9+9+14}{16}=\tfrac{120}{16}=\boxed{7{,}5}$ passi, meno della metà di $n^2$: il limite è pessimistico. Assume una passeggiata simmetrica, in cui ogni passo si avvicina con probabilità esattamente $\tfrac12$; qui invece la prima clausola, quando è violata ($x_1=x_2=1$), ha entrambe le variabili diverse da $S$ e fa avanzare con probabilità $1$.

Verifica a mano di un caso: da $1000$ (solo $x_1=1$), la prima clausola violata è $\neg x_1\vee\neg x_2$? No: con $x_2=0$ è soddisfatta ($\neg x_2$ vero). La seconda $\neg x_1\vee x_2$ è violata ($x_1=1$, $x_2=0$): si cambia $x_1$ (e si è a $S$ in $1$ passo) oppure $x_2$ (si va a $1100$). Quindi $E(1000)=1+\tfrac12\cdot0+\tfrac12E(1100)$. Da $1100$ la prima clausola è violata ($x_1=x_2=1$): si va a $0100$ o a $1000$; quindi $E(1100)=1+\tfrac12E(0100)+\tfrac12E(1000)$. Da $0100$ la terza clausola $x_1\vee\neg x_2$ è violata: si va a $1100$ o a $0000$: $E(0100)=1+\tfrac12E(1100)$. Le tre equazioni danno $E(1100)=1+\tfrac12\bigl(1+\tfrac12E(1100)\bigr)+\tfrac12\bigl(1+\tfrac12E(1100)\bigr)=2+\tfrac12E(1100)$, quindi $E(1100)=4$ ✓ e $E(1000)=E(0100)=3$ ✓.

4. La catena sulle $16$ assegnazioni (con $S$ assorbente) ha matrice $P$ calcolata dalla regola; la probabilità di non essere in $S$ dopo $T$ passi, con partenza uniforme, vale:

A $T=2n^2=32$: $\boxed{0{,}0155}$, molto meno del limite $\tfrac12$ che deriva da $E[T]\le n^2$. Anche la disuguaglianza di Markov applicata al valore atteso esatto dà solo $7{,}5/32=0{,}23$: la coda reale decade molto più in fretta (la probabilità di non aver trovato $S$ si divide per circa $3$ ogni $8$ passi all'inizio e per circa $7$ tra $16$ e $32$ passi).

5. Con la clausola violata scelta a caso (invece della prima) la dinamica cambia ma l'analisi non: una clausola violata ha comunque almeno una variabile sbagliata. La simulazione con $20\,000$ prove da partenza uniforme dà in media $6{,}93$ passi (con la regola "prima clausola" il valore esatto è $7{,}5$).

Codice di verifica

import itertools, random
import numpy as np

n = 4
cl = [((0, 0), (1, 0)), ((0, 0), (1, 1)), ((0, 1), (1, 0)), ((0, 1), (2, 0)), ((0, 1), (3, 0))]   # (var, 1 = positivo)
sat = lambda c, x: any(x[v] == s for v, s in c)
S = [x for x in itertools.product((0, 1), repeat=n) if all(sat(c, x) for c in cl)]
print("soluzioni:", S)
stati = list(itertools.product((0, 1), repeat=n)); k = {x: i for i, x in enumerate(stati)}
P = np.zeros((16, 16))
for x in stati:
    if x == S[0]:
        P[k[x], k[x]] = 1; continue
    c = next(c for c in cl if not sat(c, x))             # prima clausola violata
    for v, _ in c:
        y = list(x); y[v] ^= 1; P[k[x], k[tuple(y)]] += .5
Q = np.delete(np.delete(P, k[S[0]], 0), k[S[0]], 1)
E = np.linalg.solve(np.eye(15) - Q, np.ones(15))
for x, e in zip([x for x in stati if x != S[0]], E): print(x, round(e, 4))
print("media:", E.sum() / 16)
for T in (8, 16, 32, 64):
    print(T, 1 - (np.ones(16) / 16 @ np.linalg.matrix_power(P, T))[k[S[0]]])

Output (estratto): soluzioni: [(0, 0, 0, 0)], media: 7.5, e per $T=8,16,32,64$ le probabilità $0{,}3149$, $0{,}1161$, $0{,}01545$, $0{,}000233$.