Modèle de subcube aléatoire

Cette séance de cours présente le modèle de subcube aléatoire (RSM) comme un modèle de jouet pour les problèmes de satisfaction des contraintes. Le RSM reproduit la structure des espaces de solution dans des problèmes aléatoires de k-satisfiabilité et de couleur k, en subissant des transitions de phase similaires. Les paramètres a et p du modèle jouent un rôle crucial dans la définition des variables gelées et libres à l'intérieur des clusters, avec une densité de contrainte représentative et p déterminant la probabilité de congélation variable. La séance de cours se penche sur les propriétés du RSM, telles que l'entropie interne, la distribution des clusters et les transitions de phase, éclairant sa signification dans la compréhension des problèmes d'optimisation combinatoire.