Soddisfacibilità approssimata

[rand]

Consideriamo un insieme finito di variabili $ \{ A_{1}, A_{2}, \ldots, A_{n} \} $ che possono assumere valori nell'insieme {Vero, Falso}. Sull'insieme {Vero, Falso} definiamo le usuali operazioni booleane $ \vee $ (OR) e $ \neg $ (NOT) ( $ a \vee b $ è vera sse almeno una tra a e b è vera, $ \neg a $ è vera sse a è falsa).

Chiamiamo "clausola" un'espressione costituita o da una sola variabile o da una variabile negata o dall'OR di un insieme di variabili e variabili negate, ad esempio le seguenti sono clausole: $ A_{1}, \neg A_{1}, A_{1} \vee \neg A_{4} \vee A_{7}, $ etc... Dato un insieme di $ m $ clausole contenenti ciascuna almeno $ k $ variabili distinte dimostrare che esiste un assegnamento di valori di verità alle variabili $ \{ A_{1}, A_{2}, \ldots, A_{n} \} $ tale che al massimo $ \lceil m/2^{k} \rceil $ clausole sono false.