Conjetura de juegos únicos

Problema no resuelto en la teoría de la complejidad computacional

Problema sin resolver en informática :

¿Es verdadera la conjetura de los juegos únicos?

(más problemas sin resolver en informática)

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 cierto tipo de juego, conocido como juego único , tiene una complejidad computacional NP-dura . Tiene amplias aplicaciones en la teoría de la dificultad de la aproximación . Si la conjetura de los juegos únicos es verdadera y P ≠ NP, ^[4] entonces para muchos problemas importantes no solo es imposible obtener una solución exacta en tiempo polinomial (como postula el problema P versus NP ), sino también imposible obtener una buena aproximación en tiempo polinomial. Los problemas para los que se cumpliría un resultado de inaproximabilidad de este tipo 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 dividido casi por igual sobre si es cierta o no. ^[1]

Formulaciones

La conjetura de los juegos únicos puede enunciarse de varias maneras equivalentes.

Cubierta de etiqueta única

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-dureza 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 etiquetas con restricciones únicas sobre un alfabeto de tamaño k se puede representar como un grafo dirigido junto con una colección de permutaciones π _e : [ k ] → [ k ], una para cada arista e del grafo. Una asignación a una instancia de cobertura de etiquetas otorga a cada vértice de G un valor en el conjunto [ k ] = {1, 2, ... k}, a menudo llamados “colores”.

• 
  Una instancia de cobertura 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.
• 
  Una solución para la instancia de cubierta de etiqueta única.

Estas 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, 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 se puede resolver en tiempo polinomial.

• 
  Una instancia de cubierta de etiqueta única que no permite una asignación satisfactoria.
• 
  Una asignación que satisface todos los bordes excepto el borde grueso. Por lo tanto, esta instancia tiene el valor 3/4.

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

Más formalmente, el problema de cobertura de etiquetas con espacio entre ( c , s ) y restricciones únicas es el siguiente problema de promesa ( L _sí , L _no ):

• L _sí = { G : Alguna asignación satisface al menos una c -fracción de restricciones en G }
• L _no = { G : Cada asignación satisface como máximo una s -fracción de restricciones en G }

donde G es una instancia del problema de cobertura de etiquetas con restricciones únicas.

La conjetura de juegos únicos establece que para cada par suficientemente pequeño de constantes ε ,  δ  > 0, existe una constante k tal que el  problema de cobertura de etiquetas con espacio (1 − δ ,  ε ) y restricciones únicas sobre un alfabeto de tamaño k es NP-duro .

En lugar de gráficos, el problema de la cubierta de etiquetas se puede formular en términos de ecuaciones lineales. Por ejemplo, supongamos que tenemos un sistema de ecuaciones lineales sobre los números enteros módulo 7:

${\displaystyle {\begin{aligned}x_{1}&\equiv 2\cdot x_{2}{\pmod {7}},\\x_{2}&\equiv 4\cdot x_{5}{\pmod {7}},\\&{}\ \ \vdots \\x_{1}&\equiv 2\cdot x_{7}{\pmod {7}}.\end{aligned}}}$

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 ₁ ) = 2 x ₂  módulo 7.

Sistemas de prueba con dos probadores

Un juego único es un caso especial de un juego de una ronda con dos probadores (2P1R) . 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 tiene que 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 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 se cumple con sus preguntas y respuestas.

Un juego de una ronda con dos probadores se denomina juego único si por cada pregunta y cada respuesta del primer jugador hay exactamente una respuesta del segundo jugador que da como resultado una victoria para los jugadores, y viceversa. El valor de un juego es la probabilidad máxima de victoria para los jugadores con todas las estrategias.

La conjetura de los juegos únicos establece que para cada par suficientemente pequeño de constantes ε ,  δ  > 0, existe una constante k tal que el siguiente problema de promesa ( 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 .

Pruebas comprobables probabilísticamente

Alternativamente, la conjetura de 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 una complejidad de consulta de 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 establece que para cada par de constantes suficientemente pequeño existe una constante tal que cada problema en NP tiene una prueba probabilísticamente comprobable sobre un alfabeto de tamaño con complejidad de completitud , solidez y aleatoriedad que es un juego único. ${\displaystyle \varepsilon ,\delta >0}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle 1-\delta }$ ${\displaystyle \varepsilon }$ ${\displaystyle O(\log n)}$

Pertinencia

Algunas afirmaciones muy naturales e intrínsecamente interesantes sobre cuestiones como la votación y la espuma surgieron del estudio del UGC... Incluso si el UGC resulta ser falso, ha inspirado mucha investigación matemática interesante.

—  Ryan O'Donnell , ^[1]

La conjetura de juegos únicos fue introducida por Subhash Khot en 2002 para avanzar en ciertas cuestiones de la teoría de la dificultad de aproximación .

La verdad de la conjetura de los juegos únicos implicaría la optimalidad de muchos algoritmos de aproximación conocidos (suponiendo que P ≠ NP). Por ejemplo, la razón de aproximación lograda por el algoritmo de Goemans y Williamson para aproximar el corte máximo en un grafo es óptima dentro de cualquier constante aditiva suponiendo la conjetura de los juegos únicos y P ≠ NP.

En la tabla adyacente se muestra una lista de resultados que se sabe que implica la conjetura de 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. ${\displaystyle c+\varepsilon }$ ${\displaystyle c-\varepsilon }$ ${\displaystyle c}$

Discusión y alternativas

Actualmente, no hay consenso sobre la veracidad de la conjetura de los juegos únicos. Se han refutado algunas versiones más sólidas 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 polinómico (pero quizás no para los NP-hard). Esta forma de la conjetura aún sería útil para aplicaciones en la dificultad de aproximación. ${\displaystyle 1-\delta }$ ${\displaystyle \varepsilon }$

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 la afirmación correspondiente es verdadera por el teorema de repetición paralela, incluso cuando . ${\displaystyle \delta >0}$ ${\displaystyle \delta =0}$

Marek Karpinski y Warren Schudy han construido esquemas de aproximación temporal lineal para instancias densas de problemas de juegos únicos. ^[19]

En 2008, Prasad Raghavendra demostró que si la conjetura de los juegos únicos es verdadera, 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 polinómica. ^[20]

En 2010, Prasad Raghavendra y David Steurer definieron el problema de expansión de conjuntos pequeños en brechas y conjeturaron que es NP-hard . Esta conjetura implica la conjetura de juegos únicos. ^[21] También se ha utilizado para demostrar la 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 temporal subexponencial para el problema de juegos únicos. ^[23]

En 2012, se demostró que distinguir instancias con valor como máximo de instancias con valor como mínimo es NP-difícil. ^[24] ${\displaystyle {\tfrac {3}{8}}+\delta }$ ${\displaystyle {\tfrac {1}{2}}}$

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 como mínimo . ^[27] ${\displaystyle \delta }$ ${\displaystyle {\tfrac {1}{2}}}$

Notas

1. Klarreich, Erica (6 de octubre de 2011), "Aproximadamente difícil: la conjetura de los juegos únicos", Simons Foundation , consultado el 29 de octubre de 2012
2. Lipton, Dick (5 de mayo de 2010), "Unique Games: A Three Act Play", La carta perdida de Gödel y P=NP , consultado el 29 de octubre de 2012
3. Khot, Subhash (2002), "Sobre el poder de los juegos únicos de 2 probadores y 1 ronda", Actas del trigésimo cuarto simposio anual de la ACM sobre teoría de la computación , págs. 767–775, doi :10.1145/509907.510017, ISBN 1-58113-495-9, Número de identificación del sujeto  207635974
4. La conjetura de los juegos únicos es vacuamente verdadera si P = NP, ya que entonces todo problema en NP también sería NP-difícil.
5. Feige, Uriel ; Goemans, Michel X. (1995), "Aproximación del valor de dos sistemas de prueba de comprobación, con aplicaciones a MAX 2SAT y MAX DICUT", Proc. 3.er Simposio Israelí sobre Teoría de la Computación y los Sistemas , IEEE Computer Society Press, págs. 182–189
6. Håstad, Johan (1999), "Algunos resultados de inaproximabilidad óptima", Journal of the ACM , 48 (4): 798–859, doi :10.1145/502090.502098, S2CID  5120748.
7. Brakensiek, Joshua; Huang, Neng; Zwick, Uri (2024). "Aproximación estricta de MAX 2-SAT y relativos, bajo UGC". Simposio ACM-SIAM sobre algoritmos discretos . arXiv : 2310.12911 .
8. Goemans, Michel X .; Williamson, David P. (1995), "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida", Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 , S2CID  15794408
9. Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "¿Resultados de inaproximabilidad óptimos para MAX-CUT y otros CSP de dos variables?" (PDF) , SIAM Journal on Computing , 37 (1): 319–357, doi :10.1137/S0097539705447372, S2CID  2090495
10. Khot, Subhash ; Minzer, Dor; Safra, Muli (2018), "Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta", 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , págs. 592–601, doi :10.1109/FOCS.2018.00062, ISBN 978-1-5386-4230-6, Número de identificación del sujeto  3688775
11. Khot, Subhash ; Regev, Oded (2003), "La cobertura de vértices podría ser difícil de aproximar dentro de 2 −  ε ", IEEE Conference on Computational Complexity : 379–
12. Even, G.; Naor, J .; Schieber, B .; Sudan, M. (1998), "Aproximación de conjuntos de retroalimentación mínima y multicortes en gráficos dirigidos", Algorithmica , 20 (2): 151–174, doi :10.1007/PL00009191, MR  1484534, S2CID  2437790
13. Dinur, Irit ; Safra, Samuel (2005), "Sobre la dificultad de aproximar la cobertura mínima de vértices" (PDF) , Annals of Mathematics , 162 (1): 439–485, doi :10.4007/annals.2005.162.439 , consultado el 5 de marzo de 2010 .
14. Guruswami, Venkatesan; Manokaran, Rajsekar; Raghavendra, Prasad (2008), "Superar el orden aleatorio es difícil: inaproximabilidad del subgrafo acíclico máximo", 49.° Simposio anual IEEE sobre fundamentos de la informática, FOCS 2008, 25-28 de octubre de 2008, Filadelfia, PA, EE. UU ., págs. 573–582, doi :10.1109/FOCS.2008.51, ISBN 978-0-7695-3436-7, Número de identificación del sujeto  8762205
15. Berger, Bonnie ; Shor, Peter W. (1997), "Límites estrictos para el problema del subgrafo acíclico máximo", Journal of Algorithms , 25 (1): 1–18, doi :10.1006/jagm.1997.0864, ​​MR  1474592
16. Newman, A. (junio de 2000), Aproximación del subgrafo acíclico máximo (tesis de maestría), Instituto Tecnológico de Massachusetts, citado por Guruswami, Manokaran y Raghavendra (2008)
17. Chor, Benny ; Sudan, Madhu (1998), "Un enfoque geométrico de la intermediación", SIAM Journal on Discrete Mathematics , 11 (4): 511–523 (electrónico), doi :10.1137/S0895480195296221, MR  1640920.
18. Charikar, Moses ; Guruswami, Venkatesan ; Manokaran, Rajsekar (2009), "Cada CSP de permutación de aridad 3 es resistente a la aproximación", 24.ª Conferencia Anual IEEE sobre Complejidad Computacional , págs. 62-73, doi :10.1109/CCC.2009.29, ISBN 978-0-7695-3717-7, MR  2932455, S2CID  257225.
19. Karpinski, Marek; Schudy, Warren (2009), "Esquemas de aproximación de tiempo lineal para el juego de Gale-Berlekamp y problemas de minimización relacionados", Actas del cuadragésimo primer simposio anual de la ACM sobre teoría de la computación , págs. 313–322, arXiv : 0811.3244 , doi : 10.1145/1536414.1536458, ISBN 9781605585062, Número de identificación del sujeto  6117694
20. Raghavendra, Prasad (2008), "¿Algoritmos óptimos y resultados de inaproximabilidad para cada CSP?" (PDF) , en Dwork, Cynthia (ed.), Actas del 40.º Simposio anual de la ACM sobre teoría de la computación, Victoria, Columbia Británica, Canadá, 17-20 de mayo de 2008 , Association for Computing Machinery, págs. 245-254, doi :10.1145/1374376.1374414, ISBN 978-1-60558-047-0, Número de identificación del sujeto  15075197
21. Raghavendra, Prasad; Steurer, David (2010), "Expansión de grafos y la conjetura de juegos únicos" (PDF) , STOC'10—Actas del Simposio Internacional ACM de 2010 sobre Teoría de la Computación , Association for Computing Machinery, págs. 755–764, doi :10.1145/1806689.1806792, ISBN 978-1-4503-0050-6, MR  2743325, S2CID  1601199
22. Manurangsi, Pasin (2017), "Inaproximabilidad de máxima arista biclique, máxima biclique equilibrada y mínima k -corte a partir de la hipótesis de expansión de conjuntos pequeños", en Chatzigiannakis, Ioannis; Indyk, Piotr ; Kuhn, Fabian; Muscholl, Anca (eds.), 44.º Coloquio internacional sobre autómatas, lenguajes y programación (ICALP 2017) , Leibniz International Proceedings in Informatics (LIPIcs), vol. 80, Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, págs. 79:1–79:14, doi : 10.4230/LIPIcs.ICALP.2017.79 , ISBN 978-3-95977-041-5
23. Arora, Sanjeev ; Barak, Boaz; Steurer, David (2015), "Algoritmos subexponenciales para juegos únicos y problemas relacionados", Journal of the ACM , 62 (5): Art. 42, 25, doi :10.1145/2775105, MR  3424199, S2CID  622344. Previamente anunciado en FOCS 2010.
24. O'Donnell, Ryan ; Wright, John (2012), "Un nuevo punto de NP-dureza para juegos únicos", Actas del Simposio ACM de 2012 sobre teoría de la computación (STOC'12) , Nueva York: ACM, págs. 289–306, doi :10.1145/2213977.2214005, ISBN 978-1-4503-1245-5, MR  2961512, S2CID  6737664.
25. Klarreich, Erica (24 de abril de 2018), "Primeros grandes pasos para demostrar la conjetura de los juegos únicos", Quanta Magazine
26. Barak, Boaz (10 de enero de 2018), "Conjetura de juegos únicos: ¿a mitad de camino?", Windows On Theory , consultado el 15 de marzo de 2023
27. Khot, Subhash ; Minzer, Dor; Safra, M. (octubre de 2018), "Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta", 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , págs. 592–601, doi :10.1109/FOCS.2018.00062, ISBN 978-1-5386-4230-6, Número de identificación del sujeto  3688775

Referencias

• Khot, Subhash (2010), "Sobre la conjetura de juegos únicos", Actas de la 25.ª Conferencia IEEE sobre complejidad computacional (PDF) , págs. 99-121, doi :10.1109/CCC.2010.19.