Esercizio - MAX-SAT con clausole miste e aspettative condizionate

Teoria: Metodo probabilistico - valore atteso, alterazioni e derandomizzazioneMetodo probabilistico: se un oggetto casuale ha una proprietà con probabilità positiva (o una variabile ha media mu, quindi qualche esito la raggiunge) allora l'oggetto esiste; taglio di almeno |E|/2, MAX-SAT con 7/8, limite inferiore di Ramsey R(k,k) > 2^(k/2), alterazioni (insiemi indipendenti, Ramsey), derandomizzazione con le aspettative condizionate, lemma locale di Lovász solo enunciato.Metodo probabilistico - valore atteso, alterazioni e derandomizzazione → (MAX-SAT e derandomizzazione), Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →.

Testo. Si consideri la formula in forma normale congiuntiva su $x_1,\dots,x_5$ con $8$ clausole:

$D_1=x_1\lor x_2$, $D_2=\lnot x_1\lor x_3$, $D_3=\lnot x_2\lor\lnot x_3\lor x_4$, $D_4=x_2\lor x_3\lor\lnot x_5$, $D_5=\lnot x_3\lor x_4\lor x_5$, $D_6=x_1\lor\lnot x_4\lor x_5$, $D_7=\lnot x_1\lor\lnot x_2\lor\lnot x_5$, $D_8=x_4\lor\lnot x_5$.

1. Con un'assegnazione uniforme, qual è il numero atteso di clausole soddisfatte? Cosa si deduce sull'esistenza di un'assegnazione?
2. Applicare il metodo delle aspettative condizionate nell'ordine $x_1,\dots,x_5$ (a parità, scegliere vero), riportando a ogni passo le due attese.
3. Calcolare per enumerazione quante assegnazioni soddisfano $5,6,7,8$ clausole e confermare la media.
4. Dimostrare che ogni CNF ha un'assegnazione che soddisfa almeno metà delle clausole, e che $\frac12$ non si può migliorare con clausole da un letterale.

Soluzione

1. Attesa iniziale. Una clausola con $\ell$ letterali su variabili distinte è soddisfatta con probabilità $1-2^{-\ell}$. Qui $D_1,D_2,D_8$ hanno $\ell=2$ (probabilità $\frac34$) e $D_3,\dots,D_7$ hanno $\ell=3$ (probabilità $\frac78$): $$E=3\cdot\frac34+5\cdot\frac78=\frac94+\frac{35}8=\frac{53}8=\boxed{6{,}625}.$$ Quindi esiste un'assegnazione che soddisfa almeno $\lceil6{,}625\rceil=7$ clausole.

2. Aspettative condizionate. Per un'assegnazione parziale ogni clausola vale $1$ se ha un letterale vero, altrimenti $1-2^{-\ell'}$ con $\ell'$ letterali ancora liberi (e $0$ se non ne restano).

• $x_1$. Con $x_1=$ vero: $D_1=1$, $D_2$ ha solo $x_3$ libero: $\frac12$, $D_3,D_4,D_5$ tre liberi: $\frac78$ ciascuna, $D_6=1$, $D_7$ ha $2$ liberi: $\frac34$, $D_8$: $\frac34$. Somma $1+\frac12+3\cdot\frac78+1+\frac34+\frac34=\frac{53}8$. Con $x_1=$ falso: $D_1=\frac12$, $D_2=1$, $D_3,D_4,D_5=\frac78$, $D_6=\frac34$, $D_7=1$, $D_8=\frac34$, somma ancora $\frac{53}8$ (la media delle due attese deve valere $\frac{53}8$, e qui sono uguali): parità, si sceglie vero.
• $x_2$ (con $x_1=$ vero): vero dà $\frac{51}8$, falso dà $\frac{55}8$. Dettaglio per falso: $D_1=1$, $D_2=\frac12$, $D_3=1$ ($\lnot x_2$ vero), $D_4=\frac34$, $D_5=\frac78$, $D_6=1$, $D_7=1$, $D_8=\frac34$: somma $\frac{55}8$. Si sceglie falso.
• $x_3$: vero $\frac{15}2$, falso $\frac{25}4$. Si sceglie vero (con $x_3$ vero si soddisfa $D_2$ e $D_4$).
• $x_4$: vero $8$, falso $7$. Si sceglie vero: restano soddisfatte tutte le clausole con $x_4$ ($D_3,D_5,D_8$).
• $x_5$: vero $8$, falso $8$ (parità): vero.

Assegnazione finale $(x_1,\dots,x_5)=(1,0,1,1,1)$: tutte e $8$ le clausole sono soddisfatte. L'attesa è andata $6{,}625\to6{,}625\to6{,}875\to7{,}5\to8\to8$ senza mai scendere.

Controllo diretto: $D_1$ ($x_1$ vero) ✓, $D_2$ ($x_3$) ✓, $D_3$ ($x_4$) ✓, $D_4$ ($x_3$) ✓, $D_5$ ($x_4$) ✓, $D_6$ ($x_1$) ✓, $D_7$ ($\lnot x_2$) ✓, $D_8$ ($x_4$) ✓.

3. Enumerazione. Sulle $32$ assegnazioni, quelle che soddisfano $5,6,7,8$ clausole sono rispettivamente $4,10,12,6$; la media è $\frac{5\cdot4+6\cdot10+7\cdot12+8\cdot6}{32}=\frac{212}{32}=6{,}625$ ✓. Il caso migliore (tutte e $8$) si realizza in $6$ assegnazioni, quindi il metodo ne ha trovata una; peggior caso $5$ clausole. Un'assegnazione casuale soddisfa tutte le clausole con probabilità $\frac6{32}=0{,}1875$.

4. Metà delle clausole. Una clausola con $\ell\ge1$ letterali è soddisfatta con probabilità $1-2^{-\ell}\ge\frac12$, quindi in una CNF di $m$ clausole l'attesa è $\ge\frac m2$ e esiste un'assegnazione che ne soddisfa almeno $\lceil\frac m2\rceil$. Non si può fare meglio in generale: la formula $(x)\land(\lnot x)$ ha $m=2$ clausole e ogni assegnazione ne soddisfa esattamente $1=\frac m2$.

Codice di verifica

from fractions import Fraction
from collections import Counter
from itertools import product

F = [[(1, 1), (2, 1)], [(1, -1), (3, 1)], [(2, -1), (3, -1), (4, 1)], [(2, 1), (3, 1), (5, -1)],
     [(3, -1), (4, 1), (5, 1)], [(1, 1), (4, -1), (5, 1)], [(1, -1), (2, -1), (5, -1)], [(4, 1), (5, -1)]]

def attesa(parziale):
    tot = Fraction(0)
    for c in F:
        liberi = 0
        for v, s in c:
            if v not in parziale:
                liberi += 1
            elif parziale[v] == (s > 0):
                tot += 1
                break
        else:
            tot += 1 - Fraction(1, 2 ** liberi)
    return tot

print(attesa({}))
p = {}
for v in range(1, 6):
    e1, e0 = attesa({**p, v: True}), attesa({**p, v: False})
    print(v, e1, e0)
    p[v] = e1 >= e0
print(p, attesa(p))
print(sorted(Counter(int(attesa(dict(zip(range(1, 6), a)))) for a in product((False, True), repeat=5)).items()))

Risultato: 53/8, poi le righe 1 53/8 53/8, 2 51/8 55/8, 3 15/2 25/4, 4 8 7, 5 8 8, l'assegnazione {1: True, 2: False, 3: True, 4: True, 5: True} 8 e la distribuzione [(5, 4), (6, 10), (7, 12), (8, 6)].