Algoritmo randomizzato per problema di soddisfazione 2KCNF

Question

Il problema: lascia che una formula in $ varphi in 2kcnf $ dove c'è un incarico $ alpha $ tale che per ogni clausola, $ l $ in $ varphi $, $ alpha $ soddisfa almeno $ k $ letterali di $ l $. Suggerisci un algoritmo randomizzato per trovare un incarico soddisfacente per tale $ varphi $.

Quindi fondamentalmente ho letto del $ walkkat $ algoritm che inizia con qualche incarico casuale, $ alpha_1 $ e per ogni iterazione sceglie casualmente una clausola insoddisfatta, $ l $ di $ varphi ( alpha) $ e un letterale di $ l $. Quindi, lancia questo letterale in $ alpha_1 $, ottenendo un nuovo incarico, $ alpha_2 $.

Ripetiamo questo processo entro un tempo limitato $ t $ o fino a quando non è stato trovato un incarico soddisfacente.

Ho capito che questo algoritmo potrebbe essere adatto qui. Devo dimostrare che esiste una probabilità di $ frac {1} {2} $ che trova un incarico soddisfacente (probabilmente dopo l'amplificazione)

Penso che dovremmo guardare alla distanza di Hamming di $ alpha, alpha^t $ dove $ alpha $ è l'incarico come descritto nella domanda e $ alpha^t $ è un incarico insoddisfacente dopo $ t $ iterazioni.

Sarei felice se potessi guidare da questo punto.

Grazie!