Die Unique-Games-Vermutung: Ein überraschend umstrittenes Problem in der Komplexitätstheorie
2002 von Subhash Khot vorgeschlagen, postuliert die Unique-Games-Vermutung (UGC), dass die Approximation des Werts einer bestimmten Art von Spiel, bekannt als Unique Game, NP-schwer ist. Diese Vermutung hat erhebliche Auswirkungen auf die Theorie der Approximationsalgorithmen; wenn sie wahr ist und P≠NP, würden viele wichtige Probleme keine guten Polynomialzeitapproximationen zulassen, nicht nur exakte Lösungen. Die wissenschaftliche Gemeinschaft ist sich in ihrer Gültigkeit uneinig, mit äquivalenten Formulierungen, darunter Label-Cover- und Max2Lin(k)-Probleme. Obwohl stärkere Versionen widerlegt wurden, hat die Erforschung der UGC erhebliche mathematische Forschung angeregt, und einige Fortschritte wurden bei ihrem Beweis erzielt, einschließlich des Beweises einer verwandten Vermutung, der 2-2-Games-Vermutung.
