Étiquette : SAT

Les algorithmes PPZ et PPSZ

Publié le par Balise2 commentaires

Aujourd’hui, on va causer 3-SAT, et on va en particulier causer de deux algorithmes très voisins, les  algorithmes PPZ et son petit frère PPSZ.

Il est plus que temps que je m’attaque à ce billet que j’aurais dû écrire depuis longtemps déjà. C’est un billet qui me tient à cœur parce que ça fait un an et demi que je fais des trucs autour de ces algorithmes, et que je commence à en avoir une assez bonne idée 🙂

Rappelons un peu de formalisme, histoire qu’on sache tous de quoi on est en train de parler. Pour une intro avec un peu plus de détails, voir mon billet sur SAT. J’ai n variables x_1,..., x_n, et j’ai des formules qui sont de ce type:

(x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_3 \vee x_4) \wedge (x_6 \vee x_7 \vee x_8) \wedge ...

et je veux déterminer si, étant donné une telle formule, il existe des valeurs pour les variables x_1 à x_n (on parle d’une affectation) qui permettent d’évaluer la formule à 1 (on dit alors que la formule est satisfaite). Dans le cas général, c’est un problème NP-complet ; on a donc peu de chance de trouver un algorithme efficace qui marche à tous les coups. C’est bien le « à tous les coups » qui m’intéresse ici : je me demande ce que je peux garantir pour mon algorithme, même si je tombe sur la formule la plus difficile du monde. Le « record » actuel pour ce type de garantie est actuellement pour l’algorithme PPSZ, qui est un algorithme aléatoire, et qui est le sujet de ce billet. Comme je parle d’algorithme aléatoire, il me paraît un poil plus intuitif de parler de probabilité de succès que de temps d’exécution même si, on l’a vu, les deux notions sont liées – puisqu’il suffit de répéter un algorithme aléatoire avec une probabilité de succès donnée suffisamment de fois pour être raisonnablement sûr qu’il réussisse. Ça fait un peu Shadok, mais passons. Je vais aussi, dans ce qui suit, supposer que j’ai une formule pour laquelle je sais qu’il existe un ensemble de valeurs qui la satisfont, et que je veux « juste » trouver les valeurs en question. En pratique, les deux problèmes sont liés aussi : je peux supposer que si mon algorithme trouve ces valeurs, ben c’est qu’elles existent, et que si je cherche suffisamment longtemps sans les trouver, ça serait quand même pas de bol qu’elles existent et que je les aie ratées.

L’algorithme aléatoire le plus simple auquel on peut penser est de prendre des valeurs au hasard, de vérifier si elles satisfont la formule, et de recommencer si c’est pas le cas. Toutes les affectations possibles ont la même probabilité (si je les choisis au hasard comme ça) – et j’en ai 2^n – parce que pour chaque variable, j’ai deux possibilités, 0 ou 1. Donc la probabilité de succès de cet algorithme, si j’ai \ell affectations qui satisfont ma formule, est de \ell / 2^n : parmi les 2^n choix que je peux faire, j’en ai \ell qui marchent.

Après, il y a moyen de faire les choses de manière un peu plus intelligente. Plutôt que d’affecter les variables toutes en même temps, je vais les affecter une à une. Qu’est-ce que ça change ? Ça change que si j’ai un truc qui est trivialement idiot à faire, je peux éviter de le faire. Ce qui veut dire qu’il faut que j’explique ce que ça veut dire « trivialement idiot ». Supposons que j’aie une formule très simple qui soit juste (x_1 \vee x_2 \vee x_3). Si j’ai choisi pour x_1 la valeur 0 et pour x_2 la valeur 0, il est « trivialement idiot » de choisir 0 pour x_3 puisque je n’ai alors aucune chance de satisfaire la formule. Donc par « trivialement idiot », je veux dire qu’il y a une clause qu’il n’y a plus qu’une seule chance de satisfaire, c’est-à-dire qu’on a déjà affecté des valeurs à deux variables sur les trois de la clause, et que la clause n’est toujours pas satisfaite. Si j’utilise mon algorithme précédent, j’ai une probabilité 7/8 de trouver une affectation satisfaisante (parce qu’avec probabilité 1/8 je tombe sur 000 pour mes variables et ma formule n’est pas satisfaite). Si j’essaie d’éviter les trucs trivialement idiots… ben déroulons le truc. Je commence par x_1, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. Je continue par x_2 ; là encore, il n’y a pas de truc trivialement idiot à éviter, donc je prends une valeur au hasard. J’arrive à x_3, et là j’ai deux possibilités. Si x_1 et x_2 ont été mis tous les deux à 0, j’ai un truc trivialement idiot à éviter, c’est de mettre x_3 à 0, donc j’évite ça, je mets x_3 à 1, et ma formule est satisfaite. Si x_1 ou x_2 a été mis à 1, quoi que je fasse sur x_3 sera valide, donc je ne peux pas me tromper. Sur ce cas spécifique, rien qu’en évitant les trucs trivialement idiots, mon algorithme passe à une probabilité de succès de 1.

C’est pas toujours aussi idyllique, évidemment – là les choses se passent bien parce que j’ai une seule clause, beaucoup d’affectations valides, et qu’on est contents. Maintenant, un cas un peu plus sioux : considérons la formule

(x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee x_2 \vee \bar x_3) \wedge (x_1 \vee \bar x_2 \vee x_3) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge (\bar x_1 \vee x_2 \vee x_3) \wedge (\bar x_1 \vee x_2 \vee \bar x_3)

Deux affectations satisfont cette formule : x_1 = 1, x_2 = 1, x_3 = 0  et x_1 = 1, x_2 = 1, x_3 = 1. Avec mon algorithme « simple », la probabilité de succès est de 2/8 = 1/4. Avec mon algorithme qui cherche à éviter les trucs « trivialement idiots »… aussi, dans certaines conditions. Si je commence par la variable x_1 et que je la mets à 0, je n’ai aucune chance d’obtenir une affectation satisfaisant la formule. Si je continue par la variable x_2 et que je la mets à 0, idem. Donc il faut que je mette x_1 et x_2 à 1 tous les deux, ce qui arrive avec une probabilité 1/4 ; x_3 peut être mis à n’importe quelle valeur, donc si on n’a pas fait d’erreur jusqu’ici on n’en fera pas non plus à la dernière étape. Dans ce cas, donc, la probabilité de succès avec ou sans la détection de trucs « trivialement idiots » est la même. Sauf que… si on traite les variables non pas dans cet ordre là mais, par exemple, dans l’ordre x_3 x_2 x_1… Pour la première variable, x_3, on ne peut pas faire d’erreur, quelle que soit la valeur d’affectation. Pour x_2, on ne peut pas détecter de truc trivialement idiot, donc on la met à la bonne valeur avec une probabilité 1/2. Mais si cela arrive, la clause (x_1 \vee \bar x_2 \vee \bar x_3) ou la clause (x_1 \vee \bar x_2 \vee x_3) (selon la valeur affectée à x_3) indiquera à l’algorithme que mettre x_1 à 0 est trivialement idiot, ce qu’il faut éviter. Avec cet ordre de variables, la probabilité de succès de notre algorithme amélioré passe à 1/2. Il y a donc de « bons » ordres de variables et de « mauvais » ordres de variables (on parle de permutations). Comme il est difficile de savoir avant de commencer si une permutation est bonne ou mauvaise (ou comment trouver une bonne permutation), on fait comme d’habitude : on prend une permutation au hasard et on espère qu’en moyenne ça marche bien.

C’est exactement ce que fait l’algorithme PPZ (nommé d’après ses trois auteurs, Ramamohan Paturi, Pavel Pudlák et Francis Zane, dans un papier intitulé Satisfiability Coding Lemma) :

  • On part d’une formule F sur n variables, et on commence avec une affectation vide (on n’affecte aucune valeur aux variables pour l’instant).
  • On choisit un ordre aléatoire pour les variables, et on les traite une par une dans cet ordre :
    • Pour la variable courante x_i, si x_i = 0 est trivialement idiot, on affecte 1 à x_i
    • Sinon, si x_i = 1 est trivialement idiot, on affecte 0 à x_i
    • Sinon, on affecte une valeur aléatoire à x_i
    • Et on passe à la variable suivante.
  • Si l’affectation qu’on trouve satisfait la formule, c’est terminé ! Sinon, on recommence au départ.

L’analyse de la probabilité de succès de l’algorithme est relativement simple. Sans rentrer dans les détails, l’idée c’est que si je n’ai pas le choix pour une variable (c’est-à-dire si la mettre à 0 ou à 1 fait que l’affectation ne peut pas être satisfaisante), alors j’ai au moins une clause qui rend ce choix trivialement idiot dans au moins une permutation sur trois (parce que dans un cas sur trois, la variable en question arrivera en dernier dans la clause en question). J’ai toujours des choix aléatoires pour certaines variables, donc l’algorithme peut toujours se vautrer lamentablement, mais la probabilité de ne pas se vautrer est meilleure que si on prend juste une affectation au hasard.

Après, le lecteur attentif se sera peut-être dit « ouiiii mais si j’assigne x_1 à 1, j’ai à la fois une clause (\bar x_1, x_2, x_3) et une clause (\bar x_1, x_2, \bar x_3), donc quelque part c’est AUSSI trivialement idiot de mettre x_2 à 0… ». Le lecteur attentif est un petit malin. Et c’est aussi, quelque part, ce que fait l’algorithme PPSZ (nommé d’après les trois auteurs précédents + Michael Saks, dans un papier intitulé An Improved Exponential-Time Algorithm for k-SAT) : plutôt que de regarder les clauses une à une pour voir si par hasard on peut éliminer un choix trivialement idiot, on en regarde beaucoup à la fois (typiquement \log \log n, où n est le nombre de variables de la formule) pour tenter d’en tirer les mêmes conclusions. il y a un nombre sous-exponentiel d’ensembles de \log \log n clauses, et examiner chacun d’entre eux peut se faire en temps sous-exponentiel aussi (on peut se contenter de regarder toutes les valeurs possible pour le sous-ensemble de variables qui interviennent dans ce sous-ensemble de clauses). Les mauvais choix ne peuvent plus nécessairement être qualifiés de « trivialement idiots » mais peut-être de « manifestement idiots » ; le résultat est le même : si on peut les détecter, autant les éviter. Pour le coup, l’analyse de la probabilité de succès de cet algorithme est (beaucoup) plus complexe ; pour la petite histoire, lorsque l’article original a été publié, les auteurs n’avaient établi la probabilité de succès que dans le cas où la formule n’avait qu’une seule affectation satisfaisante (l’analyse du cas général n’arrivait à prouver qu’une probabilité de succès plus basse). La preuve plus générale a été établie par Timon Hertli (3-SAT Faster and Simpler – Unique-SAT Bounds for PPSZ Hold in General), mais il s’est passé plus de dix ans entre l’introduction de l’algorithme et la preuve en question. Une version « lisible » (pour une certaine définition de « lisible, admettons-le) de la preuve en question est disponible dans ma thèse de semestre (chapitre 2) – elle est difficile à résumer en moins de, mettons, 8 pages (heu, déjà 8 pages, c’est challenge, en fait.)

J’ai travaillé autour de ces algorithmes depuis un an et demi (pas complètement par hasard, Timon dont je parle précédemment étant doctorant à l’ETH… et mon superviseur sur tout ce que j’ai fait), et pour le coup c’est probablement LE sujet sur lequel je me sens prête à répondre à BEAUCOUP de questions 🙂

 

Deux mémoires

Publié le par BaliseLaisser un commentaire

Hier soir, j’ai fait un truc vachement bien : j’ai vaguement mis à jour ma page personnelle. J’en ai profité pour la déplacer sur un autre serveur, pour faire un peu de nettoyage, et surtout pour y publier les deux mémoires sur lesquels j’ai travaillé depuis un peu plus d’un an.

Le premier est un « mémoire de semestre » : on a la possibilité, à l’ETH, d’obtenir des crédits pour un module « Research in Computer Science » (recherche en informatique, donc), qui est en théorie un mini-projet de recherche. Comme je sais pas faire les choses à moitié, le mémoire en question fait une petite centaine de pages et il est possible qu’il explose le record du nombre de pages sur ce genre d’exercice. À ma décharge, ledit projet consistait à reprendre deux mémoires précédents par deux étudiants et à les réintégrer dans un cadre commun avec une notation développée entre temps. Le mémoire s’intitule Understanding the PPSZ algorithm for ClSP.

Le deuxième est mon mémoire de master – i.e. le projet de 6 mois à la fin des études. Celui-ci s’intitule Towards the derandomization of the PPSZ algorithm for the multiple satisfying assignments case, et il a même un zouli DOI (et ça, c’est classe, quand même.) Les deux projets sont liés (d’ailleurs on est en train de faire rentrer des morceaux du deuxième mémoire dans le premier mémoire pour tenter de publier tout ça), au sens où ils tournent tous les deux autour d’un même thème assez spécifique, mais les deux mémoires sont assez différents. Le premier était plus un boulot de lecture / compréhension / vérification / réécriture, avec assez peu de contenu original. Le deuxième mémoire était un boulot nettement plus exploratoire, et contient par ailleurs BEAUCOUP de résultats de type « on a essayé ça, ben ça marche pas. Ou alors pas trivialement. ».

Je ne vais pas rentrer tout de suite dans les détails et les explications de ce que racontent ces deux bidules – je ferai un billet plus tard sur le sujet pour essayer d’expliquer un peu ; pour ceux que ça intéresse, ça a essentiellement à voir avec SAT et avec un algorithme qui s’appelle PPSZ (et il faudrait sans doute que j’écrive la page Wikipedia de PPSZ, ne serait-ce que parce que ça me donnerait un truc à lier ici). Mais c’est une histoire pour une autre fois 🙂

Problèmes NP-complets

Publié le par Balise5 commentaires

Dans un billet précédent, j’ai tenté d’expliquer avec brio (je vous laisse choisir le verbe qualifié par « avec brio ») le problème « P = NP ». J’y ai donné une définition de la classe NP, que je répète ici : NP est la classe des problèmes pour lesquels, pour chaque instance de type « oui », on peut me convaincre en temps polynomial que la réponse est « oui » en me fournissant une preuve que c’est effectivement le cas. Et en fin de billet, j’ai vaguement mentionné la notion de problème NP-complet.

La définition usuelle de problème NP-complet, c’est un problème qui est « dans NP » et « NP-difficile ». Je vais donc expliquer ce que veut dire NP-difficile 🙂 De façon informelle, c’est un problème qui est au moins aussi difficile que tous les problèmes de la classe NP. Une autre façon informelle de dire ça, c’est qu’il est aussi difficile qu’un autre problème NP-difficile. Le problème de cette définition, c’est qu’il faut bien commencer quelque part, et avoir un premier problème NP-difficile pour le comparer aux autres.

L’archétype des problèmes NP-difficiles (et donc NP-complets, parce que SAT est dans NP), c’est le problème SAT, dont j’ai parlé dans le billet précédent. C’est pas évident, a priori, que SAT est NP-difficile. Mais on peut montrer que même 3-SAT est NP-difficile : 3-SAT représente les instances de SAT où toutes les clauses ont exactement trois littéraux ((Les avis diffèrent sur la terminologie exacte. De nombreux auteurs définissent 3-SAT comme les instances de SAT où toutes les clauses ont au plus deux littéraux. J’appelle ça (sur la suggestion de mon prof de SAT) <=3-SAT. Dans le cas présent ça m’arrange de définir sur exactement 3 littéraux, donc je fais ça, OK ?)). Je ne vais en pas expliquer la preuve, parce que ça impliquerait que je passe pas mal de temps à expliquer des choses que j’ai pas fondamentalement envie d’expliquer. Pour les gens intéressés par la question, ça a été démontré en 1971 et c’est connu sous le nom de Théorème de Cook-Levin.

Maintenant qu’on en a un, on peut en trouver d’autres par réduction. On réduit un problème NP-difficile (par exemple SAT) à un autre problème qu’on veut prouver NP-difficile, appelons le A. Pour faire ça, on démontre que si on peut résoudre A efficacement, c’est-à-dire en temps polynomial, alors on peut résoudre SAT efficacement.

L’idée générale de ce genre de preuve, c’est qu’on prend une instance quelconque du problème NP-difficile, et on la transforme, en temps polynomial, en instance du problème A qui permette de conclure sur l’instance originale. Maintenant, supposons qu’on sache résoudre le problème A (c’est-à-dire n’importe quelle instance du problème A) en temps polynomial. Alors on peut prendre n’importe quelle instance de SAT, la transformer en une instance du problème A, résoudre l’instance du problème A, et conclure. La transformation se fait en temps polynomial, la résolution de A se fait en temps polynomial, la somme des deux est polynomiale, donc on sait résoudre n’importe quelle instance de SAT en temps polynomial, donc on sait résoudre SAT en temps polynomial. Facile.

Les problèmes NP-complets sont donc, en quelque sorte, « équivalents » en terme de complexité : si on sait en résoudre un en temps polynomial, alors on peut résoudre tous les autres en temps polynomial aussi, et on peut résoudre tous les problèmes de NP en temps polynomial (puisqu’ils sont aussi difficiles que tous les problèmes de la classe NP). Donc, si on trouve un moyen de résoudre en temps polynomial toutes les instances d’un problème NP-complet… on a démontré que P = NP. Et gagné un million de dollars. Et surpris beaucoup, beaucoup de monde.

Il y a toute une série de problèmes pour lesquels on sait qu’ils sont NP-difficiles, ou NP-complets si en plus ils sont dans NP. Il y a des gens qui s’intéressent à des problèmes… exotiques, dirons-nous ; je vais juste laisser quelques liens pour les gens intéressés et que ça fera rigoler :

Passé cet interlude amusant, je vais donner un exemple de réduction pour prouver que le problème CLIQUE est NP-complet. C’est probablement l’exemple bateau que tout le monde donne quand il parle de ce genre de chose, mais il doit y avoir une raison à ça (la raison en est que le problème est raisonnablement facile à décrire et que la réduction est relativement simple par rapport à ce qu’on peut voir ailleurs). Le truc que j’explique ici est largement repompé du CLRS, c’est-à-dire le Cormen, Leiserson, Rivest & Stein, c’est-à-dire Introduction to Algorithms, traduit en français sous le nom Algorithmique (je ne sais pas ce que vaut cette traduction) – c’est le bouquin de référence de BEAUCOUP de cours d’algorithmique.

Donc, le problème CLIQUE est le suivant : étant donné un graphe (un ensemble de sommets et d’arcs) G, contient-il une clique de taille k ? Une clique de taille k, c’est un ensemble de k sommets qui sont tous reliés les uns aux autres. Par exemple (vous m’excuserez, je recycle mes figures), ce machin-là est est une clique de taille 8. Notons au passage qu’il contient également une clique de taille 1 (un seul sommet), 2 (un arc), 3 (un triangle), 4, 5, 6 et 7, puisqu’on peut trouver des ensembles de sommets de cette taille qui sont tous reliés les uns aux autres.

8clique

On veut réduire 3-SAT à ce problème ; comme 3-SAT est NP-difficile, CLIQUE est NP-difficile aussi. CLIQUE est dans NP, parce que si je donne k sommets, c’est facile de vérifier que ces k sommets sont effectivement tous reliés les uns aux autres. Donc, si CLIQUE est NP-difficile, CLIQUE est NP-complet.

Pour attaquer ma réduction, je prends une formule 3-SAT. Je prends une formule 3-SAT CNF (j’ai expliqué ce que ça veut dire dans mon article sur SAT), c’est-à-dire une formule qui a cette tête là :

(x_1 \vee x_2 \vee x_3) \wedge (\bar x_2 \vee x_4 \vee \bar x_5) \wedge (x_1 \vee \bar x_2 \vee \bar x_3) \wedge ...

c’est-à-dire un ensemble de m clauses composées d’au plus 3 littéraux reliés par des OU, et les clauses étant reliées par des ET.

À partir de là, on crée un graphe contenant 3*m sommets. Chacun de ces sommets correspond à un littéral de la formule, éventuellement dupliqué. Pour visualiser les choses plus facilement, ça peut peut-être aider de grouper les sommets en groupes de trois. Dans l’exemple de la formule ci-dessus, ça donne les sommets suivants :

x_1, x_2, x_3~;\bar x_2, x_4, \bar x_5~; x_1, \bar x_2, \bar x_3

Ensuite, on ajoute des arcs partout. Enfin, presque partout. On n’ajoute pas d’arcs dans les « groupes » correspondant aux clauses. On n’ajoute pas non plus d’arcs entre les littéraux qui ne sont pas « compatibles », c’est-à-dire l’inverse l’un de l’autre. Si j’ai deux littéraux x_1 et \bar x_1, je ne crée pas d’arc entre eux. Pour ma mini-formule au-dessus, voilà ce que donne le graphe en question :

clique3sat1

et voilà les arcs qui ne sont PAS dans le graphe précédent :

clique3sat2

Et maintenant qu’on a ce graphe là, l’idée, c’est que la formule SAT peut être satisfaite si et seulement si le graphe (le premier) a une clique de taille m (m étant le nombre de clauses de la formule SAT). J’ai donc deux choses à prouver :

  • si la formule peut être satisfaite, alors le graphe a une clique de taille m
  • si le graphe a une clique de taille m, la formule peut être satisfaite.

On va commencer par le premier point. Supposons que la formule puisse être satisfaite. Donc, on peut affecter une valeur à toutes les variables de sorte que la formule soit satisfaite. Par conséquent, toutes les clauses peuvent être satisfaites par cette affectation. Donc, dans chaque clause, il existe un littéral qui a pour valeur 1 (le littéral « positif », par exemple x_1 si la variable a la valeur 1, le littéral « négatif », par exemple \bar x_1 si la variable a la valeur 0). On considère, dans chaque « groupe » de sommets du graphe défini précédemment, le sommet correspondant à ce littéral (si plusieurs littéraux ont la valeur 1, on en prend un au pif). Comme on prend un sommet par groupe, et qu’on a m groupes, on arrive à m sommets. On veut maintenant montrer qu’il y a un arc entre toutes les paires de sommets de cet ensemble de sommets. Or, les deux raisons pour lesquelles on pourrait ne pas en avoir, c’est soit que les sommets sont dans le même groupe, soit qu’ils sont incompatibles. On ne peut pas avoir choisi deux sommets dans le même groupe, puisqu’on en a choisi exactement un par groupe. Et on ne peut pas avoir choisi deux sommets incompatibles, parce qu’ils correspondraient à des littéraux x_i et \bar x_i, qu’on n’a choisi que des littéraux qui ont la valeur 1, et qu’on ne peut pas avoir en même temps x_i = 1 et \bar x_i = 1. Donc, toutes les paires dans les m sommets sont connectées entre elles, donc on a une clique de taille m, ce qu’on voulait démontrer.

Donc, on peut passer au deuxième point : si le graphe a une clique de taille m, la formule peut être satisfaite. Supposons, donc, que le graphe ait une clique de taille m. Comme les sommets d’un même groupe ne sont pas connectés entre eux, les sommets sont forcément dans des groupes différents. Si on a une clique de taille m, ça veut dire qu’on a un sommet dans chaque groupe de sommets. On peut donner à tous ces sommets la valeur 1. On ne peut pas avoir de clique qui contienne des sommets x_i et \bar x_i, puisqu’il n’y a pas d’arc entre deux sommets de ce type et que, par définition d’une clique, il faut que tous les arcs soient présents. Donc, si une clique de taille m existe, ça veut dire qu’on a trouvé un littéral par clause qui peut valoir 1, et que tous ces littéraux sont compatibles entre eux. Et donc qu’on peut satisfaire la formule correspondant au graphe, ce qu’on voulait démontrer aussi.

Donc, si on peut résoudre CLIQUE en temps polynomial, alors on peut résoudre SAT en temps polynomial ; SAT étant NP-difficile, CLIQUE l’est aussi, et donc CLIQUE est NP-complet, ce qui termine la preuve.

Le caractère NP-complet d’un problème est, quelque part, une « preuve » de la difficulté du problème en question, mais il faut atténuer ça largement. Déjà, ça ne présume en rien de la difficulté d’une instance donnée du problème. Ça ne présume en rien de la difficulté sur une certaine classe d’instances non plus. J’explique. Dire que CLIQUE est difficile, ça ne veut pas dire que, par exemple, décider si un triangle (qui est une clique de taille 3) est dans un graphe, même un gros graphe, est difficile. Parce que je peux prendre tous les ensembles de trois sommets, regarder s’ils forment un triangle, et conclure. Les ensembles de trois sommets, il y en a à peu près n³ dans un graphe à n sommets (plus exactement, il y en a n(n-1)(n-2)/6, mais, bon, à peu près n³), du coup je peux décider ça en temps polynomial (je fais n³ opérations qui vont pas prendre des plombes, c’est-à-dire vérifier si trois arcs donnés sont effectivement dans le graphe). Du coup, je peux décider 3-CLIQUE en temps polynomial. Bon, c’est pas pour ça que je vais être millionnaire, hein. Parce que le problème CLIQUE, il se limite pas à 3. Cela dit, si je veux, je peux aussi décider 1000-CLIQUE (clique de taille 1000) en temps polynomial. Bon, c’est un polynôme de degré 1000, mais on s’en fout 🙂

Par contre, dans le cas général, je ne peux pas décider si un graphe sur n sommets contient une clique de n/2 sommets, ou n/10000 sommets, ou même log n sommets en temps polynomial avec cet algorithme qui regarde tous les groupes de taille k (donc ici k = n/2, n/10000 ou log n) et qui regarde les arcs dans le groupe, parce que ça impliquerait de faire respectivement à peu près n^{n/2}, n^{n/10000} et n^{\log n} opérations, et que dans tous les cas c’est pas polynomial. Et, de manière générale, personne ne sait si c’est possible de faire ça en temps polynomial, puisque CLIQUE est NP-complet et qu’on ne sait pas si P est égal à NP. Beaucoup de gens supposent que non, mais personne ne sait.

Même là, ça ne présume en rien de la difficulté d’une instance donnée d’un problème. Supposons qu’on me file un graphe qui se trouve contenir n(n-1)/2 arcs pour n sommets. Alors je peux décider, sans trop de problème, que oui, ce graphe contient une clique de taille n/2, n/10000 et log n. Parce qu’un graphe de n(n-1)/2 arcs pour n sommets, ben il contient tous les arcs possibles pour le graphe : c’est un graphe complet (une clique sur n sommets), et comme une clique sur k sommets est un sous-graphe d’une clique sur n sommets… ben c’est pas bien difficile de répondre à la question. Idem si on me file un graphe avec 0 arcs et n sommets, je vais pas avoir beaucoup de mal à répondre que non, il ne contient pas de clique de taille n/2.

Dans le cas de SAT, on n’a aucun problème à résoudre les instances de 2-SAT (où toutes les clauses contiennent deux littéraux) en temps polynomial (et même linéaire). Il y a aussi des instances de SAT qui sont « faciles », par exemple celles où il y a peu de dépendances entre les clauses : on sait qu’on peut les résoudre, et on sait même comment (et, pour les gens intéressés, par « peu de dépendances », j’entends « qui tombent dans le cas du Lovász local lemma, dont l’application à SAT n’est pas évidente d’après la définition de la Wikipedia, mais qui devrait être plus claire ici).

De manière générale, il peut même être non trivial de créer des instances de problèmes NP-complets qu’on ne sait pas résoudre en temps polynomial. Notons au passage que c’est pas facile de prouver qu’on ne sait pas résoudre une instance donnée en temps polynomial. On peut exhiber des instances de problèmes qui sont difficiles (i.e. exponentielles) pour un algorithme donné, et triviales pour d’autres algorithmes…

Et c’est un peu ce qui se passe en pratique : on a des instances de problèmes pour lesquels on sait que le cas général est NP-complet (ou pire), et qu’on résout pourtant tous les jours en pratique. Une des raisons peut être que le problème est « petit » (c’est pas un drame de coller un algorithme exponentiel sur un problème de taille 4, quoi), mais ça peut aussi être parce que le problème fait partie d’une sous-classe d’instances sur laquelle le problème est facile. Donc, conclure qu’une instance de problème est difficile parce que le problème général l’est et abandonner (parce qu’on saura pas faire), c’est pas forcément une bonne idée, parce qu’il se peut qu’on n’ait pas considéré qu’on se trouve dans une restriction facile du problème !

Bref, comme d’habitude, « c’est pas aussi simple que ça ». En ce moment, je fais de la théorie, et du coup je m’intéresse plutôt aux problèmes eux-mêmes plutôt qu’à des instances données. Mais c’est parfois salutaire de se souvenir que des trucs « difficiles en théorie » peuvent s’avérer « faciles en pratique », ça change des trucs faciles en théorie qu’on sait pas faire en pratique… 🙂

Le problème SAT

Publié le par Balise15 commentaires

Je vais expliquer un peu ce qu’est le problème SAT, parce que j’aurai l’occasion d’en reparler plus en détail bientôt (pour une certaine définition de bientôt dépendant de ma charge scolaire 🙂 ). C’est aussi une des briques fondamentales liées à la question « P = NP » ; j’avais commencé à écrire ce billet dans un prochain billet à propos de problèmes NP-complets, mais je crois que je peux faire un billet complet sur le sujet, ça m’évitera d’avoir la tentation de « faire vite ». L’autre raison pour laquelle je veux pas faire vite, c’est que je fais en ce moment un « projet de semestre » sur un sujet très très très voisin, et comme j’ai aussi l’intention de faire un billet sur ce que je fais plus précisément, ben ça ça sera fait.

SAT est une abréviation pour « boolean satisfiability problem », ou en français « problème de satisfaisabilité booléenne ». L’idée, c’est qu’on a une formule booléenne, ou formule SAT, et qu’on cherche à décider si on peut la résoudre ou pas.

Une formule SAT peut, par exemple, avoir cette tête là :

(x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)

Il y a plusieurs éléments dans ce machin. Le premier élément, ce sont les variables – ici, x, y, z. On peut les voir comme les « inconnues » d’une équation : on veut ici savoir si on peut trouver des valeurs pour x, y et z. En plus de ça, on est dans un univers un peu bizarre, l’univers booléen : x, y et z ne peuvent prendre que la valeur 0 ou la valeur 1.

Après, il y a des symboles bizarres. \vee, ça veut dire « ou », et \wedge, ça veut dire « et ». Les petites barres au-dessus de certaines lettres indiquent un négation. Les symboles se lisent comme ça :

\begin{array}{|c|c||c|c|c|c|} \hline x & y & \bar x &\bar y & x \vee y & x \wedge y \\ \hline 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 0 & 1 & 1 & 0 & 1 & 0 \\ \hline 1 & 0 & 0 & 1 & 1 & 0 \\ \hline 1 & 1 & 0 & 0 & 1 & 1 \\ \hline \end{array}

Ou, si j’écris ça en toutes lettres :

  • si x = 1, alors \bar x = 0, sinon \bar x = 1 (\bar x prend la valeur inverse de x)
  • si x = 1, alors x \vee y = 1 ; si y = 1 alors x \vee y = 1 ; si x = 0 et y = 0, alors x \vee y = 0 (« x OU y vaut 1 »). Il faut préciser que quand on dit « ou » dans ce contexte, ce n’est pas dans le même sens que « fromage ou dessert » : si on prend du fromage et du dessert, alors on prend du fromage ou du dessert (puisqu’on prend au moins l’un des deux). 
  • si x = 1 et y = 1, alors x \wedge y = 1, sinon x \wedge y = 0 (« x ET y valent tous les deux 1 »).

On peut combiner tous ces machins de la manière qu’on veut pour obtenir des formules booléennes. On s’intéresse en particulier aux formules du type que j’ai donné précédemment, qui sont appelées des formules « CNF » (pour « conjunctive normal form »). Ce type de formule est défini comme un ensemble de clauses, toutes reliées entre elles par des symboles \wedge (« et »). Une clause se compose d’un ou plusieurs littéraux (un littéral, des littéraux), qui sont soit une variable (par exemple x), soit sa négation (par exemple bar x) tous reliés entre eux par des symboles \vee (« ou »). On veut donc que toutes les clauses aient comme valeur 1 (parce qu’on veut que la première ET la deuxième ET la troisième ET toutes les suivantes aient la valeur 1). Et le fait que chaque clause ait la valeur 1, ça se traduit par le fait qu’au moins un des littéraux de la formule ait la valeur 1 (parce qu’on veut que le premier littéral OU le deuxième OU le troisième OU… ait la valeur 1). Même remarque que précédemment, il peut arriver que tous les littéraux aient la valeur 1, ça renvoie quand même toujours 1. 

La question posée par une instance de SAT, c’est « est-ce que je peux trouver des valeurs pour toutes les variables de manière à ce que la formule complète ait pour valeur 1 ? ».

Reprenons l’exemple précédent, et nommons la formule F:

F = (x \vee y \vee z) \wedge (\bar x \vee \bar y) \wedge (\bar x \vee y \vee z)

Si je veux regarder s’il existe des valeurs pour x, y et z qui font que la formule F vaut 1 (c’est-à-dire pour que la formule soit satisfaite), je peux toutes les énumérer et regarder ce qu’il se passe.

\begin{array}{|c|c|c||c|c|c||c|} \hline x & y & z & x \vee y \vee z & \bar x \vee \bar y & \bar x \vee y \vee z & F \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1\\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 0 & 1 & 0\\ \hline \end{array}

Mon petit tableau répond à la question « est-ce qu’il existe des valeurs pour x, y et z de sorte à ce que la formule F vaille 1 » (la réponse est oui), et il va même plus loin en donnant lesdites valeurs (par exemple, x = 1, y = 0, z = 1 sont des valeurs valides pour satisfaire la formule).

Le problème, c’est que c’est pas vraiment gérable dès qu’on commence à avoir beaucoup de variables. La raison, c’est que pour chaque variable, il faut que je regarde ce qu’il se passe pour sa valeur 0 et pour sa valeur 1. Donc j’ai deux choix pour la première variable ; deux choix pour la deuxième variable ; deux choix pour la troisième variable, etc. Les choix en question se multiplient : on voit ça dans le tableau au-dessus, il faut que je fasse une ligne pour toutes les combinaisons possibles de valeurs de variables. Donc, pour 3 variables, 2*2*2 = 2³ = 8 lignes. Pour 5 variables, on est déjà à 2*2*2*2*2 = 2⁵ = 32 lignes, et ça commence à être relou à faire à la main. Pour 20 variables, on est à 2²⁰ = 1.048.576 lignes, et ça commence à ne pas être vraiment instantané à calculer. Et ça augmente de plus en plus vite : les joies de la fonction puissance.

Pour ceux qui ont suivi les explications précédentes, ce n’est PAS un algorithme en temps polynomial ; c’est un algorithme en temps exponentiel. D’autant plus que je ne considère là que l’énumération de tous les cas et que je ne regarde même pas combien de temps il me faut pour conclure dans chacun des cas.

Du point de vue « classe de complexité », SAT fait partie des problèmes de la classe NP. Si on me donne une formule et des valeurs pour toutes les variables de la formule, je peux vérifier efficacement que, effectivement, ça marche : je peux vérifier qu’une formule peut être satisfaite si on m’en fournit la preuve.

Par contre, on ne sait pas s’il fait partie des problèmes de la classe P : on ne sait pas s’il existe un algorithme polynomial permettant de décider si, oui ou non, une formule peut être satisfaite ou non. On ne sait pas non plus s’il est en dehors des problèmes de la classe P : on ne sait pas s’il faut nécessairement un algorithme « plus puissant » qu’un algorithme polynomial pour le résoudre. Et répondre à cette question (et le prouver correctement) permettrait de répondre à la question « est-ce que P = NP ? » – mais pour ça, il faut que je parle de problèmes NP-complets, et je ferai ça dans le prochain billet 🙂

EDIT : bon, je re-précise un ou deux trucs, parce que tripa a pas COMPLÈTEMENT tort dans les commentaires. Quand je dis « on ne sait pas si », je veux parler du cas général, c’est-à-dire de n’importe quelle formule SAT. Après, il y a des cas où c’est « facile », c’est-à-dire qu’on peut conclure très vite. C’est par exemple le cas si on se restreint à des clauses avec deux littéraux (2-SAT) : dans ce cas précis, il y a un algorithme qui permet de conclure en temps linéaire (c’est-à-dire, en gros, qu’on lit la formule, et qu’on sait.) La difficulté intrinsèque du problème général ne donne pas vraiment d’indication sur les instances individuelles. C’est plutôt un point que je traiterai dans le billet suivant, parce que c’est aussi important de s’en souvenir, mais, bon. Tout ça pour dire que SAT c’est dur, mais qu’il y a des instances du problème qui sont faciles, et qu’il faut éventuellement se poser les bonnes questions avant de conclure qu’on n’a aucune chance de résoudre une formule donnée 🙂

Random insomniac thoughts about sudoku, CSPs and SAT

Publié le par Balise

(Writing in English because for some reason (probably the fact that my courses on the subject are in English) my inner monologue is in English on this subject, so…)

This post will probably be fairly obscure to… err… I’d say anyone but me, but that would be kind of pretentious 😉 Let’s just say that if you haven’t heard the acronyms SAT or CSP before, you can probably skip this post, unless you’re very curious. If you have questions, remarks, don’t hesitate. I have no idea what I’m doing either.

Last night I did some Project Euler problems before going to bed, and I inadvertantly clicked on this one: Problem 96 – Devise an algorithm for solving Su Doku puzzles. And while I know that I shouldn’t go to bed with a problem I’m able to easily formulate in my head, I did anyway (because it was late), and an hour or two of mild insomnia followed, because I was thinking of said problem. Typical. Or, as I put it a while ago, « don’t derive and try to sleep ».

This is a collection of random thoughts on the subject; I obviously didn’t give it A LOT of thought, it’s more of a general interrogation post, because I think the exercise in itself isn’t bad. Also, I haven’t hit the litterature at all – so there’s a fair chance I’m only saying stuff that’s either trivial, stupid or wrong 😉

The problem of regular 9×9 sudoku, per se, is « easy ». Well, it’s not « easy » in that I’d probably need some hours of thought and a some hours of sweat implementing it, but I’m pretty confident I could get there, at least for a decent approximation of a decent algorithm. But anything I’m saying from now on doesn’t have anything to do with the question of solving a given 9×9 sudoku in a « reasonable » amount of time – I’m only interested in the « theoretical » problem.

What’s not obvious to me is the « best » way to model and solve the associated CSP or SAT instance. Again, for a « regular » sudoku, one could argue that the size of the problem is constant and that the « best » way to model and solve doesn’t matter much since it will also be constant. However, since I’m (originally) interested in solving the Project Euler question, the size of the constant actually matters to me – if it’s « gazillions », it’s not good enough for me. Moreover, the Sudoku problem for nxn problems is known to be NP-complete (haven’t read that paper yet, intend to). Also note that I’m not that interested in the decision problem (« is there a solution to this instance of sudoku ») but in finding an assignment that actually solves said puzzle.

There are two straightforward ways to model sudoku:

  • as a regular CSP problem, where each variable represents a cell and can take a value between 1 and n.
  • as a SAT problem where we define n boolean variables for each cell, each of which saying « does this cell take this value? »

A priori, both models have their merits; the CSP has the advantage of compactness and (human) readability, and the SAT has the advantage of being boolean (duh). Note that in any case, any nxn problem can be modelled in same way (by expressing the constraints of the grid, which is very regular), and the particular instance of the puzzle can be seen as an initial partial assignment on the problem (which will remove some constraints and some variables in some constraints). I’m not entirely clear on the number of constraints in both cases, I’d need some time with a pen and paper for that. Also, considering a SAT problem, the exact number of variables in a « reasonable » 3SAT reduction would need some work also. Probably not « hard » work, but « careful » work (and I’m not that good at careful 😉 ).

Now if I consider that I have a model, what are my options? (Again, this is a worst-case analysis – there’s a fair chance that most « real-world » puzzles won’t need that kind of machinery, but some instances ARE hard (the problem IS NP-complete). But by the way, what makes an « easy » sudoku puzzle, and is it possible to decide whether a given instance is easy or not? Anyway, for the general case, the three possibilities that I’m thinking of right now are randomized algorithms, so any runtime I’m talking about is expected runtime.

  • Apply PPSZ (beware, it bites) to the (3-)SAT problem. A bound on the runtime here would be 1.308^k, where k is the number of variables that I haven’t computed yet.
  • Use a PPZ-like approach on the CSP instance – consider a random permutation of the variables and treat them in order; pick, for each variable, a value uniformly at random in those that are not forbidden by the current partial assignment.
  • Use a « random downsampling » approach (for each cell, keep two values uniformly at random) and apply PPZ to the resulting instance.

Those two last approaches were part of an exercise in the latest SAT graded sheet I (tried to) solve(d), so I have some idea on how the analysis would go through in that case. It would still need some work, obviously (especially since the problem is slightly different).

Another question is, since the problem is very structured, can I use this structure to my advantage to make the algorithm faster, prove that the general algorithm is faster in this particular setting, or to get an easier analysis?

Still in the « random questions » – sudoku can be seen as the problem of « rainbow coloring » a n-regular hypergraph where each vertex is part of exactly 3 edges. How would previous algorithms behave on a more general case? (non n-regular and/or with an arbitrary number of edges per vertex). This kind of reflexion gives me the intuition that indeed, the structure of the problem can be used to get better algorithms and/or bounds. But I may obviously be wrong.

Last one, and then I’m leaving you 😉 – this is a more general question regarding SAT vs CSP. SAT domains and constraints and stuff can be represented in a hypercube where every possible assignment is a vertex and two vertices are connected iff there differ by exactly one coordinate. The hypercube model is a nice way to look at the SAT problem from a different perspective, and definitely has its uses. Is there any geometrical structure that would be useful in the same way (or in some way) for CSPs and variables whose domain is not reduced to 2 boolean values?