Conjeturas sobre juegos únicos

La siguiente formulación de la conjetura de juegos únicos se utiliza a menudo en la dificultad de aproximación . La conjetura postula la NP-dificultad 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 ciertos pares ordenados específicos. Las restricciones únicas implican que, para cada arista, 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${\displaystyle k}$puede representarse como un grafo dirigido junto con una colección de permutaciones${\displaystyle \pi _{e}:[k]\to [k]}$uno para cada borde${\displaystyle e}$del gráfico. Una asignación a una instancia de cubierta de etiqueta da a cada vértice de${\displaystyle G}$un valor en el conjunto${\displaystyle [k]=\{1,2,\ldots ,k\}}$, a menudo llamados “colores”.

• 
  Un ejemplo de cubierta de etiqueta única. A los 4 vértices se les pueden asignar los colores rojo, azul y verde, cumpliendo las restricciones en cada arista.
• 
  Una solución para la instancia única de la cubierta de la etiqueta.

Estas instancias están fuertemente restringidas, ya que el color de un vértice define de forma única los colores de sus vecinos y, por lo tanto, de toda su componente conexa. Así, si la instancia de entrada admite una asignación válida, dicha asignación puede hallarse eficientemente iterando sobre todos los colores de un único nodo. En particular, el problema de decidir si una instancia dada admite una asignación satisfactoria puede resolverse en tiempo polinomial.

• 
  Un ejemplo de portada de etiqueta única que no permite una asignación satisfactoria.
• 
  Una asignación que satisface todas las aristas excepto la arista gruesa. Por lo tanto, esta instancia tiene un valor de 3/4.

El valor de una instancia de cobertura de etiquetas únicas es la fracción de restricciones que puede satisfacer cualquier asignación. Para instancias satisfacibles, este valor es 1 y es fácil de encontrar. Por otro lado, parece muy difícil determinar el valor de un juego insatisfacible, incluso de forma aproximada. La conjetura de los juegos únicos formaliza esta dificultad.

Más formalmente, el${\displaystyle (c,s)}$El problema de cobertura de etiquetas con huecos y restricciones únicas es el siguiente problema de promesa.${\displaystyle (L_{\text{sí}},L_{\text{no}})}$:

• ${\displaystyle L_{\text{sí}}=\{G:{\text{alguna asignación satisface al menos una }}c{\text{-fracción de restricciones en }}G\}}$,
• ${\displaystyle L_{\text{no}}=\{G:{\text{cada asignación satisface como máximo una }}s{\text{-fracción de restricciones en }}G\}}$,

dónde${\displaystyle G}$es un ejemplo del problema de la cobertura de etiquetas con restricciones únicas.

La conjetura de los juegos únicos afirma que para cada par de constantes suficientemente pequeñas${\displaystyle \varepsilon ,\delta >0}$, existe una constante${\displaystyle k}$de tal manera que el${\displaystyle (1-\delta,\varepsilon)}$-problema de etiqueta-cubierta de huecos con restricciones únicas sobre el alfabeto de tamaño${\displaystyle k}$es NP-difícil .

Consideremos el siguiente sistema de ecuaciones lineales sobre los enteros módulo${\displaystyle k}$:$${\displaystyle {\begin{aligned}a_{1}x_{1}&\equiv b_{1}\cdot x_{2}+c_{1}{\pmod {k}},\\a_{2}x_{2}&\equiv b_{2}\cdot x_{5}+c_{2}{\pmod {k}},\\&{}\ \ \vdots \\a_{m}x_{1}&\equiv b_{m}\cdot x_{7}+c_{m}{\pmod {k}}.\end{aligned}}}$$Cuando cada ecuación involucra exactamente dos variables, esta es una instancia del problema de cobertura de etiquetas con restricciones únicas; tales instancias se conocen como instancias del problema Max2Lin(k). No es inmediatamente obvio que la inaproximabilidad de Max2Lin(k) sea equivalente al UGC, pero de hecho este es el caso, por una reducción. ^{[ 5 ]} Es decir, el UGC es equivalente a: para cada par suficientemente pequeño de constantes ε , δ > 0, existe una constante k tal que el problema Max2Lin(k) con brecha (1 − δ , ε ) es NP-difícil .      

Se ha argumentado que la UGC es esencialmente una cuestión de topología computacional , ^{[ 6 ]} que involucra principios locales-globales (estos últimos también son evidentes en la demostración de la Conjetura de los Juegos 2-2, ver más abajo).

Linial ^{[ 7 ]} observó que Unique Label Cover es una instancia del problema de la Sección Máxima de un Grafo de Recubrimiento (grafos de recubrimiento es la terminología de la topología ; en el contexto de juegos únicos, estos se denominan a menudo elevaciones de grafos). Hasta la fecha, todos los problemas conocidos cuya inaproximabilidad es equivalente al UGC son instancias de este problema, incluyendo Unique Label Cover y Max2Lin(k). Cuando estos dos últimos problemas se consideran instancias de la Sección Máxima de un Grafo de Recubrimiento, la reducción entre ellos ^{[ 5 ]} preserva la estructura de los espacios de recubrimiento de grafos, ^{[ 6 ]} por lo que no solo los problemas, sino también la reducción entre ellos, tiene una interpretación topológica natural. Grochow y Tucker-Foltz presentaron un tercer problema de topología computacional cuya inaproximabilidad es equivalente al UGC: Localización de 1-Cohomología en Triangulaciones de 2-Variedades. ^{[ 6 ]}

Un juego único es un caso especial de un juego de dos probadores y una ronda (2P1R) . Un juego de dos probadores y una ronda 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 define mediante un predicado que depende de las preguntas enviadas a los jugadores y de las respuestas que estos proporcionan.

Los jugadores pueden acordar una estrategia de antemano, aunque no pueden comunicarse entre sí durante la partida. Ganan si sus preguntas y respuestas satisfacen la condición planteada.

Un juego de una ronda con dos participantes se denomina juego único si, por cada pregunta y respuesta del primer jugador, existe exactamente una respuesta del segundo jugador que resulta en una victoria para ambos, y viceversa. El valor de un juego es la probabilidad máxima de victoria para los jugadores considerando todas las estrategias.

La conjetura de los juegos únicos afirma que para cada par de constantes suficientemente pequeñas ε , δ > 0, existe una constante k tal que el siguiente problema de promesas ( L _sí , L _no ) es NP-difícil :   

• L _sí = { G : el valor de G es al menos 1 − δ}  
• L _no = { G : el valor de G es como máximo  ε}

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 verificable probabilísticamente para problemas en NP.

Un juego único puede considerarse como un tipo especial de prueba verificable probabilísticamente no adaptativa con complejidad de consulta 2, donde para cada par de posibles consultas del verificador y cada posible respuesta a la primera consulta, hay exactamente una posible respuesta a la segunda consulta que hace que el verificador acepte, y viceversa.

La conjetura de los juegos únicos afirma que para cada par de constantes suficientemente pequeñas${\displaystyle \varepsilon ,\delta >0}$hay una constante${\displaystyle K}$de tal manera que cada problema en NP tiene una prueba verificable probabilísticamente sobre un alfabeto de tamaño${\displaystyle K}$con exhaustividad${\displaystyle 1-\delta }$, solidez${\displaystyle \varepsilon }$y complejidad aleatoria${\displaystyle O(\log n)}$que es un juego único.