Conjetura de los Juegos Únicos: Un Problema Sorprendentemente Divisivo en Complejidad Computacional
Propuesta por Subhash Khot en 2002, la Conjetura de los Juegos Únicos (UGC) postula que aproximar el valor de un tipo específico de juego, conocido como juego único, es NP-difícil. Esta conjetura tiene implicaciones significativas para la teoría de los algoritmos de aproximación; si es verdadera y P≠NP, muchos problemas cruciales no permitirían buenas aproximaciones en tiempo polinomial, no solo soluciones exactas. La comunidad académica está dividida sobre su validez, con formulaciones equivalentes incluyendo problemas de cobertura de etiquetas y Max2Lin(k). Aunque versiones más fuertes han sido refutadas, la exploración de la UGC ha estimulado investigaciones matemáticas sustanciales, y se han realizado algunos progresos hacia su demostración, incluyendo la demostración de una conjetura relacionada, la conjetura de los juegos 2-2.
