L'algorithme GSAT est, pour la plupart, simple: vous obtenez une formule sous forme normale conjonctive et retournez les littéraux des clauses jusqu'à ce que vous trouviez une solution qui satisfasse la formule ou que vous atteigniez la limite max_tries / max_flips et ne trouviez aucune solution....
J'essaie d'envelopper ma tête autour d'une preuve d'exhaustivité NP qui semble tourner autour de SAT / 3CNF-SAT. C'est peut-être l'heure tardive, mais je crains de ne pas pouvoir penser à une formule 3CNF qui ne puisse être satisfaite (il me manque probablement quelque chose d'évident). Pouvez-vous...
Planar 3SAT est NP-complet. Une instance planaire 3SAT est une instance 3SAT pour laquelle le graphique construit à l'aide des règles suivantes est planaire: ajouter un sommet pour chaque et ¯ x iXjeXjex_iXje¯Xje¯\bar{x_i} ajouter un sommet pour chaque clauseCjCjC_j ajouter un bord pour chaque...
J'essaie de travailler sur une tâche (tirée du livre Algorithms - par S. Dasgupta, CH Papadimitriou et UV Vazirani , Chap 8, problème 8.6a), et je paraphrase ce qu'il dit: Étant donné que 3SAT reste NP-complet même lorsqu'il est limité à des formules dans lesquelles chaque littéral apparaît au plus...
Il existe un algorithme aléatoire très simple qui, étant donné un 3SAT, produit une assignation satisfaisant au moins 7/8 des clauses (en attente): choisissez une assignation aléatoire. Une assignation aléatoire satisfait chaque clause avec la probabilité 7/8, et donc la linéarité de l'attente...