Conjecture des jeux uniques

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

La conjecture des jeux uniques (en anglais Unique Games Conjecture) 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[modifier | modifier le code]

Coloration[modifier | modifier le code]

Système d'équations linéaires[modifier | modifier le code]

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

est un entier fixé et connu. La conjecture affirme que, pour tous , si 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 qui satisfait une proportion au moins des équations.
  2. Aucun vecteur ne satisfait une proportion supérieure à des équations.

Autres[modifier | modifier le code]

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

Applications[modifier | modifier le code]

Théorie de la complexité[modifier | modifier le code]

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 (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 à , 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 .

Autres résultats[modifier | modifier le code]

Histoire et importance[modifier | modifier le code]

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

Notes et références[modifier | modifier le code]

  1. a et b (en) Subhash Khot, « On the Unique Games Conjecture », dans Proc. IEEE 25th Conference on Computational Complexity, (ISBN 978-1-4244-7214-7, lire en ligne), p. 99-121.
  2. Étienne Ghys, « Subhash Khot, prix Nevanlinna 2014 », images des Maths, CNRS,‎ (lire en ligne).
  3. (en) Tim Gowers, « ICM2014 — Khot laudatio », sur http://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, (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. (en) « Nevanlinna Prize 2014 for Subhash Khot », sur International Mathematical Union.

Lien externe[modifier | modifier le code]

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