¿Es cierta la conjetura de los juegos únicos?
En la teoría de la complejidad computacional , la conjetura de los juegos únicos (a menudo denominada UGC ) es una conjetura hecha por Subhash Khot en 2002. [1] [2] [3] La conjetura postula que el problema de determinar el valor aproximado de un determinado tipo El juego, conocido como juego único , tiene una complejidad computacional NP-hard . Tiene amplias aplicaciones en la teoría de la dureza de aproximación . Si la conjetura de los juegos únicos es verdadera y P ≠ NP, [4] entonces, para muchos problemas importantes no sólo es imposible obtener una solución exacta en tiempo polinomial (como lo postula el problema P versus NP ), sino que también es imposible obtener una buena aproximación en tiempo polinomial. Los problemas para los que se aplicaría tal resultado de inaproximabilidad incluyen problemas de satisfacción de restricciones , que surgen en una amplia variedad de disciplinas.
La conjetura es inusual porque el mundo académico parece dividido en partes iguales sobre si es cierta o no. [1]
La conjetura de los juegos únicos se puede expresar de varias formas equivalentes.
La siguiente formulación de la conjetura de los juegos únicos se utiliza a menudo en dureza de aproximación . La conjetura postula la dureza NP del siguiente problema de promesa conocido como cobertura de etiquetas con restricciones únicas . Para cada arista, los colores de los dos vértices están restringidos a algunos pares ordenados particulares. Las restricciones únicas significan que para cada arista ninguno de los pares ordenados tiene el mismo color para el mismo nodo.
Esto significa que una instancia de cobertura 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".
Estos casos están fuertemente restringidos en el sentido de que el color de un vértice define de forma única los colores de sus vecinos y, por tanto, de todo su componente conectado. Por lo tanto, si la instancia de entrada admite una asignación válida, entonces 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 puede resolverse en tiempo polinomial.
El valor de una instancia de cubierta de etiqueta única es la fracción de restricciones que puede satisfacer cualquier asignación. Para casos satisfactorios, este valor es 1 y es fácil de encontrar. Por otra parte, parece muy difícil determinar, aunque sea aproximadamente, el valor de un juego insatisfactorio. La conjetura de los juegos únicos formaliza esta dificultad.
Más formalmente, el problema de cobertura de etiquetas con espacios ( c , s ) con restricciones únicas es el siguiente problema de promesa ( L sí , L no ):
donde G es una instancia del problema de cobertura de etiquetas con restricciones únicas.
La conjetura de los juegos únicos establece que para cada par de constantes suficientemente pequeño ε , δ > 0, existe una constante k tal que el problema de cobertura de etiquetas de espacio (1 − δ , ε ) con restricciones únicas sobre un alfabeto de tamaño k es NP -duro .
En lugar de gráficos, el problema de la cobertura de etiquetas se puede formular en términos de ecuaciones lineales. Por ejemplo, supongamos que tenemos un sistema de ecuaciones lineales sobre números enteros módulo 7:
Este es un ejemplo del problema de la cobertura de etiquetas con restricciones únicas. Por ejemplo, la primera ecuación corresponde a la permutación π (1, 2) donde π (1, 2) ( x 1 ) = 2 x 2 módulo 7.
Un juego único es un caso especial de un juego de una ronda (2P1R) con dos probadores . Un juego de una ronda con dos probadores tiene dos jugadores (también conocidos como probadores) y un árbitro. El árbitro envía a cada jugador una pregunta extraída de una distribución de probabilidad conocida , y cada jugador debe enviar una respuesta. Las respuestas provienen de un conjunto de tamaño fijo. El juego se especifica mediante un predicado que depende de las preguntas enviadas a los jugadores y de las respuestas proporcionadas por ellos.
Los jugadores pueden decidir una estrategia de antemano, aunque no pueden comunicarse entre sí durante el juego. Los jugadores ganan si el predicado queda satisfecho con sus preguntas y sus respuestas.
Un juego de una ronda con dos participantes se denomina juego único si para cada pregunta y cada respuesta del primer jugador, hay exactamente una respuesta del segundo jugador que resulta en una victoria para los jugadores, y viceversa. El valor de un juego es la probabilidad máxima de ganar para los jugadores en todas las estrategias.
La conjetura de los juegos únicos establece que para cada par de constantes suficientemente pequeño ε , δ > 0, existe una constante k tal que el siguiente problema de promesa ( L sí , L no ) es NP-difícil :
donde G es un juego único cuyas respuestas provienen de un conjunto de tamaño k .
Alternativamente, la conjetura de los juegos únicos postula la existencia de un cierto tipo de prueba probabilísticamente comprobable para problemas en NP.
Un juego único puede verse como un tipo especial de prueba no adaptativa comprobable probabilísticamente con complejidad de consulta 2, donde para cada par de consultas posibles del verificador y cada respuesta posible a la primera consulta, hay exactamente una respuesta posible a la segunda consulta que hace que el verificador acepte, y viceversa.
La conjetura de los juegos únicos establece que por cada par de constantes suficientemente pequeño hay una constante tal que cada problema en NP tiene una prueba comprobable probabilísticamente sobre un alfabeto de tamaño con complejidad , solidez y aleatoriedad, lo cual es un juego único.
Algunas afirmaciones muy naturales e intrínsecamente interesantes sobre cosas como la votación y las espumas simplemente surgieron del estudio del UGC... Incluso si el UGC resulta ser falso, ha inspirado muchas investigaciones matemáticas interesantes.
- Ryan O'Donnell , [1]
La conjetura de los juegos únicos fue introducida por Subhash Khot en 2002 para avanzar en determinadas cuestiones de la teoría de la dureza de aproximación .
La verdad de la conjetura de los juegos únicos implicaría la optimización de muchos algoritmos de aproximación conocidos (asumiendo P ≠ NP). Por ejemplo, la relación de aproximación lograda por el algoritmo de Goemans y Williamson para aproximar el corte máximo en un gráfico es óptima dentro de cualquier constante aditiva suponiendo la conjetura del juego único y P ≠ NP.
En la tabla adyacente se muestra una lista de resultados que se sabe que implica la conjetura de los juegos únicos junto con los mejores resultados correspondientes para el supuesto más débil P ≠ NP. Una constante de o significa que el resultado se cumple para cada constante (con respecto al tamaño del problema) estrictamente mayor o menor que , respectivamente.
Actualmente, no existe consenso sobre la veracidad de la conjetura de los juegos únicos. Se han refutado ciertas formas más fuertes de la conjetura.
Una forma diferente de la conjetura postula que distinguir el caso en el que el valor de un juego único es al menos del caso en el que el valor es como máximo es imposible para los algoritmos de tiempo polinomial (pero quizás no para NP-hard). Esta forma de conjetura seguiría siendo útil para aplicaciones de dureza de aproximación.
La constante en las formulaciones anteriores de la conjetura es necesaria a menos que P = NP. Si se elimina el requisito de unicidad, se sabe que el enunciado correspondiente es verdadero según el teorema de repetición paralela, incluso cuando .
Marek Karpinski y Warren Schudy han construido esquemas de aproximación de tiempo lineal para instancias densas de problemas de juegos únicos. [19]
En 2008, Prasad Raghavendra demostró que si la conjetura de los juegos únicos es cierta, entonces, para cada problema de satisfacción de restricciones, la mejor relación de aproximación viene dada por una determinada instancia de programación semidefinida simple , que es en particular polinomio. [20]
En 2010, Prasad Raghavendra y David Steurer definieron el problema de expansión Gap-Small-Set y conjeturaron que es NP-difícil . Esta conjetura implica la conjetura de los juegos únicos. [21] También se ha utilizado para demostrar una gran dureza de los resultados de aproximación para encontrar subgrafos bipartitos completos . [22]
En 2010, Sanjeev Arora , Boaz Barak y David Steurer encontraron un algoritmo de aproximación de tiempo subexponencial para el problema de los juegos únicos. [23]
En 2012, se demostró que distinguir instancias con valor como máximo de instancias con valor al menos es NP-difícil. [24]
En 2018, después de una serie de artículos, se demostró una versión más débil de la conjetura, llamada conjetura de los juegos 2-2. En cierto sentido, esto prueba "la mitad" de la conjetura original. [25] [26] Esto también mejora la brecha más conocida para la cobertura de etiquetas únicas: es NP-difícil distinguir instancias con valor como máximo de instancias con valor al menos . [27]
