Promesse Contrainte Satisfaction et Largeur

Cette séance de cours traite de la complexité des problèmes de satisfaction des contraintes de promesse (PCSP) et de leur largeur, y compris des sujets tels que la coloration approximative des graphiques, les classes de complexité, les algorithmes de cohérence locale, les polymorphismes et les réductions. L'instructeur présente les résultats du Théorème de Barto-Kozik, les faibles opérations près de l'unanimité, et les implications de la largeur sublinéaire dans les PCSP. La séance de cours explore également l'utilisation d'hypergraphies aléatoires clairsemées, l'exploitation des frontières et les implications des sous-éléments insatisfaits. En outre, il examine les implications de la largeur limitée dans les PCSP et le développement de nouveaux algorithmes pour résoudre des cas spécifiques de PCSP.