Conjecture des jeux uniques
Nom, Gender:Fem, Number:Sing, Nom féminin singulier
Morpho:withmaj, Morpho:withspace
source:wiki
Définitions
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. Subhash Khot a reçu le prix Nevanlinna en 2014 pour son travail sur cette conjecture.
