Amphi Carnot, École polytechnique.
Tous les membres d'Alcophys sont les bienvenus...
11 heures : Prise de contact
11h 15 : Exposé de R. Cori. Automates et tas de sable (pelles et petits rateaux seront fournis).
12 h 30 : déjeuner
14h : Exposé de Rémi Monasson. Transition de phase et complexité typique : le modèle de la 2+p-satisfiabilité aléatoire.
Le problème de la K-satisfiabilité (SAT) est d'importance primordiale en théorie de la complexité. Récemment, des travaux numériques et théorique ont mis en évidence l'existence de seuils pour le problème de décision associé à une formule booléenne aléatoire. Nous montrerons comment ce problème, proche des graphes aléatoires orientés, peut être étudié avec les méthodes de physique statistique des sytèmes désordonnés. Une attention particulière sera portée au paramètre d'ordre émergeant lors de cette étude et sur l'information qu'il renferme sur la structure des solutions satisfaisant les formules booléennes considérées. Après avoir introduit le modèle mixte de la 2+p-satisfiabilité, nous soulignerons l'importance fondamentale de la notion d'ordre de la transition de phase, en particulier si l'on s'attache à comprendre pourquoi SAT devient difficile à résoudre autour du seuil SAT/UNSAT.
15h : discussion sur l'organisation future.
16h : fin de la journée.