Conjecture des jeux uniques

La conjecture des jeux uniques (en anglais Unique Games Conjecture et souvent abrégée UGC) est une conjecture en théorie de la complexité, proposée par Subhash Khot en 2002. Selon cette conjecture, résoudre de manière approximative un certain problème spécifique est NP-difficile. Elle a d'importantes applications relatives à la complexité des algorithmes d'approximation ; le travail qui a été fourni autour de cette conjecture a également permis de démontrer des résultats relatifs à d'autres sujets, par exemple sur la stabilité des systèmes de vote. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture.

Formulations de la conjecture

Système d'équations linéaires

Considérons des systèmes d'équations de la forme suivante :

${\begin{aligned}x_{1}&\equiv 2+x_{2}{\pmod {n}}\\x_{2}&\equiv 4+x_{5}{\pmod {n}}\\&{}\ \ \vdots \\x_{1}&\equiv 2+x_{7}{\pmod {n}}.\end{aligned}}$

où $n$ est un entier fixé et connu. La conjecture affirme que, pour tous $\epsilon ,\delta >0$, si $n$ est assez grand, il est NP-difficile, étant donné un tel système d'équations, de dire s'il satisfait l'une ou l'autre des deux propriétés suivantes :

1. Il existe un vecteur $(x_{1},x_{2},...)$ qui satisfait une proportion au moins $1-\epsilon$ des équations.
2. Aucun vecteur $(x_{1},x_{2},...)$ ne satisfait une proportion supérieure à $\delta$ des équations.

Autres

Il existe plusieurs autres formulations équivalentes de la conjecture, faisant intervenir par exemple l'expansion d'un graphe.

Applications

Théorie de la complexité

La conjecture des jeux uniques permet de démontrer d'autres résultats selon lesquels il est NP-difficile de trouver des solutions approximatives à certains problèmes.

En particulier, si elle est vraie, elle implique qu'il est NP-difficile de résoudre approximativement le problème MAX-CUT avec un ratio d'approximation supérieur à environ $0,878$ (ce qui est le ratio atteint par l'algorithme de Goemans et Williamson).

Elle implique également qu'obtenir un ratio d'approximation strictement inférieur à $2$, pour le problème de couverture par sommets, est NP-difficile. Sans la conjecture, on peut prouver qu'il est NP-difficile d'obtenir un ratio inférieur à environ $1,36$.

Histoire et importance

La conjecture des jeux uniques a été définie dans un article de Subhash Khot en 2002. Elle est considérée comme très importante par la communauté de l'informatique théorique, par exemple Avi Wigderson a déclaré :

« The conjecture is an anchor to which we can connect an enormous number of approximation problems. It creates a theory. »

En 2014, Khot a remporté le prix Nevanlinna, l'une des grandes récompenses de mathématiques et d'informatique, pour son travail autour de ce concept.

En 2018, après une série d'articles, une version plus faible de la conjecture, appelée conjecture des jeux 2-2, a été prouvée. Dans un certain sens, cela prouve "une moitié" de la conjecture originale. Cela améliore également l'écart le plus connu pour la couverture à étiquettes uniques : il est NP-difficile de distinguer les instances avec une valeur au plus $\delta$ des instances avec une valeur au moins ${\tfrac {1}{2}}$.

Article lié

• Graphe de Frankl-Rödl

Lien externe

(en) Tim Gowers, « ICM2014 — Khot laudatio », sur gowers.wordpress.com