En la teoría de la complejidad computacional , la conjetura de juegos únicos (a menudo denominada UGC ) es una conjetura realizada por Subhash Khot en 2002. [1] [2] [3] La conjetura postula que el problema de determinar el valor aproximado de un determinado tipo de juego, conocido como un juego único , tiene una complejidad computacional NP-dura . Tiene amplias aplicaciones en la teoría de la dureza de aproximación . Si la conjetura de juegos únicos es verdadera y P ≠ NP, [4] entonces para muchos problemas importantes no solo es imposible obtener una solución exacta entiempo polinomial (como lo postula el problema P versus NP ), pero también es imposible obtener una buena aproximación de tiempo polinomial. Los problemas para los que se mantendría tal resultado de inaproximabilidad incluyen problemas de satisfacción de restricciones , que surgen en una amplia variedad de disciplinas.
La conjetura es inusual en el sentido de que el mundo académico parece estar dividido en partes iguales sobre si es cierta o no. [1]
La siguiente formulación de la conjetura de los juegos únicos se usa a menudo en la dureza de la aproximación . La conjetura postula la dureza NP del siguiente problema de promesa conocido como cobertura de etiqueta con restricciones únicas . Para cada borde, los colores en los dos vértices están restringidos a algunos pares ordenados particulares. Las restricciones únicas significan que para cada borde ninguno de los pares ordenados tiene el mismo color para el mismo nodo.
Esto significa que una instancia de cubierta de etiqueta con restricciones únicas sobre un alfabeto de tamaño k se puede representar como un gráfico dirigido junto con una colección de permutaciones π e : [ k ] → [ k ], una para cada borde e del gráfico. Una asignación a una instancia de portada de etiqueta le da a cada vértice de G un valor en el conjunto [ k ] = {1, 2, ... k}, a menudo llamado "colores".
Una instancia de portada de etiqueta única. A los 4 vértices se les pueden asignar los colores rojo, azul y verde mientras se satisfacen las restricciones en cada borde.
Tales instancias están fuertemente restringidas en el sentido de que el color de un vértice define de manera única los colores de sus vecinos y, por lo tanto, para todo su componente conectado. Por lo tanto, si la instancia de entrada admite una asignación válida, dicha asignación se puede encontrar de manera eficiente iterando sobre todos los colores de un solo nodo. En particular, el problema de decidir si una instancia dada admite una asignación satisfactoria se puede resolver en tiempo polinomial.