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[1]. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture[2].

Formulations de la conjecture

Coloration

Système d'équations linéaires

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

${\displaystyle {\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ù ${\displaystyle n}$ est un entier fixé et connu. La conjecture affirme que, pour tous ${\displaystyle \epsilon ,\delta >0}$, si ${\displaystyle 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 ${\displaystyle (x_{1},x_{2},...)}$ qui satisfait une proportion au moins ${\displaystyle 1-\epsilon }$ des équations.
2. Aucun vecteur ${\displaystyle (x_{1},x_{2},...)}$ ne satisfait une proportion supérieure à ${\displaystyle \delta }$ des équations.

Autres

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

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[1].

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 ${\displaystyle 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 à ${\displaystyle 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 ${\displaystyle 1,36}$.

Autres résultats

Histoire et importance

La conjecture des jeux uniques a été définie dans un article de Subhash Khot en 2002[4]. 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. »[5]

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[6].

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[7],[8]. 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 ${\displaystyle \delta }$ des instances avec une valeur au moins ${\displaystyle {\tfrac {1}{2}}}$[9].

Notes et références

1. (en) Subhash Khot, « On the Unique Games Conjecture », dans Proc. IEEE 25th Conference on Computational Complexity, 2010 (ISBN 978-1-4244-7214-7, lire en ligne), p. 99-121.
2. Étienne Ghys, « Subhash Khot, prix Nevanlinna 2014 », images des Maths, CNRS,‎ 2014 (lire en ligne).
3. (en) Tim Gowers, « ICM2014 — Khot laudatio », sur gowers.wordpress.com
4. (en) Subhash Khot, « On the power of unique 2-prover 1-round games », dans Proc. 34th ACM Symposium on Theory of Computing, 2002 (ISBN 978-1-58113-495-7, DOI 10.1145/509907.510017), p. 767-775.
5. (en) Erica Klarreich, « Approximately Hard: The Unique Games Conjecture », sur simonsfoundation.org, 6 octobre 2011.
6. (en) « Nevanlinna Prize 2014 for Subhash Khot »^(Archive.org • Wikiwix • Archive.is • Google • Que faire ?), sur International Mathematical Union.
7. « First Big Steps Toward Proving the Unique Games Conjecture » Quanta Magazine.
8. « Unique Games Conjecture – halfway there? » Windows on Theory.
9. Subhash Khot, Dor Minzer et Muli Safra, « Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion », 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS),‎ octobre 2018, p. 592-601 (DOI 10.1109/FOCS.2018 .00062, lire en ligne).

Article lié

• Graphe de Frankl-Rödl

Lien externe

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