Conjecture des jeux uniques

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.

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

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}$.