Nadia Creignou (SDAD)

Les phenomenes de seuil ou phenomenes de changement de phase sont bien connus en physique. Pour le probleme SAT un tel phenomene traduit le changement de phase brusque de la satisfaisabilite a l’insatisfaisabilite d’une formule CNF quand le rapport nombre de clauses sur nombre de variables varie. Nous proposons un tour d’horizon des resultats connus a ce jour pour le probleme SAT et ses variantes (2-SAT, 3-SAT, Horn-SAT, XOR-SAT …) en ce qui concerne les phenomenes de seuil.