Subhash Khot a introduit la conjecture des jeux uniques (UGC) en 2002, établissant un principe d’organisation central pour la théorie de la complexité computationnelle [1]. La conjecture se demande si un type particulier de problème de satisfaction de contraintes — attribuer des couleurs aux sommets d’un réseau sous des contraintes de permutation uniques — est NP-difficile à approximer, même légèrement [1].
Si elle est vraie, l’UGC implique que, pour une vaste classe de problèmes pratiques, trouver une solution « suffisamment bonne » est aussi difficile sur le plan computationnel que de trouver une solution parfaite [2].
Le fonctionnement des jeux uniques
Un jeu unique est un problème de couverture d’étiquettes où chaque arête entre deux sommets impose une permutation : la couleur d’un sommet détermine de façon unique la couleur de son voisin [1].
Satisfiabilité vs. difficulté
Lorsqu’une instance est parfaitement satisfiable, une coloration valide peut être trouvée efficacement en choisissant une couleur pour un sommet et en la propageant à travers le réseau [1].
La difficulté apparaît lorsque l’instance est insatisfiable. Distinguer les instances où presque toutes les contraintes peuvent être satisfaites de celles où presque aucune ne l’est semble nécessiter un temps exponentiel [1].
Définition formelle
La conjecture affirme que, pour tout petit constante ε, δ > 0, il existe une taille d’alphabet k telle que la version à écart (1−δ, ε) de ce problème soit NP-difficile [1]. Cela équivaut à l’inapproximabilité de Max2Lin(k), un système d’équations linéaires à deux variables modulo k [1].
Pourquoi la difficulté d’approximation importe
De nombreuses tâches d’optimisation réelles — comme la disposition de puces, la planification aérienne et le repliement des protéines — sont NP-difficiles, ce qui signifie que les solutions exactes sont impraticables pour de grandes instances [2].
La frontière de l’approximation
Alors que la conjecture P versus NP suggère que les solutions exactes sont probablement impossibles, l’UGC indique que même des approximations de haute qualité sont impossibles pour de nombreux problèmes [2].
L’effet « ancre »
L’UGC agit comme une ancre théorique. Supposer qu’elle est vraie permet aux chercheurs de démontrer des résultats de difficulté d’approximation serrés pour un vaste ensemble de problèmes de satisfaction de contraintes en un seul coup [2]. Avi Wigderson la décrit comme « une ancre à laquelle nous pouvons relier un nombre énorme de problèmes d’approximation » [2].
Portée interdisciplinaire
Les implications de l’UGC s’étendent au-delà de l’informatique théorique vers des domaines divers. Des chercheurs ont tiré des conséquences pour la structure des mousses, la géométrie des espaces métriques et l’analyse des systèmes de vote [2].
Ryan O’Donnell décrit la conjecture comme « la clé magique qui rend de nombreux problèmes plus simples et plus clairs », notant qu’elle a fondamentalement changé la façon dont les chercheurs abordent ces problèmes [2]. Cette fertilité suggère que l’UGC saisit une propriété structurelle fondamentale de la difficulté computationnelle [2].
État actuel et implications futures
En 2011, la communauté académique était à peu près également divisée quant à la vérité ou la fausseté de l’UGC [1]. Aucune preuve ou réfutation définitive n’est apparue, laissant la conjecture comme une question ouverte qui façonne les programmes de recherche actuels [2].
Impact d’une preuve
Une preuve fournirait des seuils de difficulté exacts pour de nombreux problèmes d’approximation. Elle confirmerait que les relâchements de programmation semi-définie — les algorithmes « suspects évidents » — sont optimaux pour tous les problèmes de satisfaction de contraintes [2].
Impact d’une réfutation
Une réfutation serait tout aussi transformative. Elle exigerait l’invention d’un algorithme d’approximation fondamentalement nouveau, différent de toute technique connue, et obligerait les chercheurs à redéfinir la véritable frontière de l’approximation [2].
Quel que soit le résultat, Richard Lipton a observé que « qu’il soit finalement démontré faux ou non change peu la brillance de la conjecture » [2].
