Algorithme randomisé pour le problème de satisfaction du 2KCNF

Question

Le problème: laissez une formule dans $ varphi in 2kcnf $ où il y a une affectation $ alpha $ telle que pour chaque clause, $ l $ dans $ varphi $, $ alpha $ satisfait au moins $ k $ littéraux de $ L $. Suggérez un algorithme randomisé pour trouver une affectation satisfaisante pour tel $ varphi $.

Donc, fondamentalement, j'ai lu le $ walksat $ algoritm qui commence par une affectation aléatoire, $ alpha_1 $ et pour chaque itération choisit au hasard une clause insatisfaite, $ l $ de $ varphi ( alpha) $ et un littéral de $ L $. Ensuite, il retourne ce littéral dans $ alpha_1 $, obtenant une nouvelle affectation, $ alpha_2 $.

Nous répétons ce processus dans un temps lié $ T $ ou jusqu'à ce qu'une affectation satisfaisante ait été trouvée.

J'ai compris que cet algorithme pourrait convenir ici. J'ai besoin de montrer qu'il y a une probabilité de $ frac {1} {2} $ pour trouver une affectation satisfaisante (probablement après amplification)

Je pense que nous devrions examiner la distance de Hamming de $ alpha, alpha ^ t $ où $ alpha $ est la mission telle que décrite dans la question et $ alpha ^ t $ est une affectation insatisfaisante après $ t $ itérations.

Je serais heureux si vous pouviez guider à partir de ce point.

Merci!