Physique statistique des syst\`emes d\'esordonn\'es et probl\`emes combinatoires al\'eatoires

Le probl\`eme de $K$-satisfiabilit\'e al\'eatoire

Le probl\`eme de $K$-satisfiabilit\'e (SAT) est d'importance primordiale en th\'eorie de la complexit\'e. R\'ecemment, des travaux num\'eriques et th\'eoriques ont mis en \'evidence l'existence de seuils pour le probl\`eme de d\'ecision associ\'e \`a une formule bool\'eenne al\'eatoire. Nous montrerons comment ce probl\`eme, proche de celui de questions sur les graphes al\'eatoires orient\'es, peut \^etre \'etudi\'e avec les m\'ethodes de physique statistique des syt\`emes d\'esordonn\'es. Une attention particuli\`ere sera port\'ee au param\`etre d'ordre \'emergeant lors de cette \'etude et sur l'information qu'il renferme quant \`a la structure des solutions satisfaisant les formules bool\'eennes consid\'er\'ees. Nous soulignerons l'importance fondamentale de la notion d'ordre de la transition de phase, en particulier lorsqu'on s'attache \`a comprendre pourquoi SAT devient difficile \`a r\'esoudre autour du seuil SAT/UNSAT.