La conjecture des jeux uniques : un problème étonnamment controversé en complexité computationnelle

Proposée par Subhash Khot en 2002, la conjecture des jeux uniques (UGC) postule qu'approximer la valeur d'un type spécifique de jeu, appelé jeu unique, est NP-difficile. Cette conjecture a des implications significatives pour la théorie des algorithmes d'approximation ; si elle est vraie et P≠NP, de nombreux problèmes cruciaux n'admettraient pas de bonnes approximations en temps polynomial, pas seulement des solutions exactes. La communauté académique est divisée sur sa validité, avec des formulations équivalentes incluant des problèmes de couverture d'étiquettes et Max2Lin(k). Bien que des versions plus fortes aient été réfutées, l'exploration de l'UGC a stimulé des recherches mathématiques substantielles, et certains progrès ont été faits vers sa démonstration, y compris la démonstration d'une conjecture connexe, la conjecture des jeux 2-2.