Résumé de séminaire

Résumé :

Un phénomène de transition de phase brusque a été mis en évidence il y a quelques années pour le problème NP-complet bien connu 3-SAT.

La probabilité qu'une formule 3-CNF aléatoire soit satisfaisable décroit brusquement quand le ratio du nombre de clauses L sur le nombre de variables n augmente. Plus précisément il existe une valeur critique c telle que si L/n < c alors la formule aléatoire est presque surement satisfaisable, alors que si L/n > c elle est presque surement insatisfaisable.

Ce comportement probabiliste a suscité beaucoup d'intérêt car il a été observé d'un point de vue pratique que les instances difficiles des problèmes NP-complets coincidaient avec la fenêtre de transition.

Nous établissons un théorème de classification croisée, complexité (P ou NP-complet) versus nature de la transition de phase (brusque ou progressive), pour les problèmes de satisfaction de contraintes booléennes. Nous proposons un critère concis et local qui, étant donné un ensemble de types de contraintes autorisées en entrée, permet de décider facilement si le problème de satisfaisabilité associé a une transition de phase brusque ou progressive.

Notre étude fournit une première preuve uniforme du fait que de nombreux problèmes de satisfaisabilité bien connus tels k-SAT, k-XOR-SAT, Non-Tous-Egaux-k-SAT, 1-parmi-k-SAT, ont une phase de transition brusque.

Références :

Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7, 2001. ISBN 0-89871-479-6. http://www.ec-securehost.com/SIAM/DT07.html

Nadia Creignou and Hervé Daudé. Random generalized satisfiability problems. Proc. of the 5th International Symposium on Theory and Applications of Satisfiability testing, SAT'2002, Cincinnati U.S.A, pages 17-26, May 2002. http://gauss.ececs.uc.edu/Conferences/SAT2002/sat2002list.html

Email : Nadia.Creignou@lidil.univ-mrs.fr