¿Es cierta la conjetura de los juegos únicos?
En la teoría de la complejidad computacional , la conjetura de 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 del juego, conocido como un 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 cierta y P ≠ NP , [4]entonces, para muchos problemas importantes, no sólo es imposible obtener una solución exacta en tiempo polinomial (como se postula en el problema P versus NP ), sino que también es imposible obtener una buena aproximación polinomial-tiempo. Los problemas para los que se mantendría tal resultado de inapropiabilidad 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 verdad o no. [1]
Formulaciones
La conjetura de los juegos únicos se puede enunciar de varias formas equivalentes.
Cubierta de etiqueta única
La siguiente formulación de la conjetura de juegos únicos se usa a menudo en dureza de aproximación . La conjetura postula la dureza NP del siguiente problema de promesa conocido como cubierta de etiqueta con restricciones únicas . Para cada borde, los colores de 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 cobertura de etiqueta con restricciones únicas sobre un alfabeto de tamaño k puede representarse 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 cubierta 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 cubierta 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.
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, de 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 puede resolverse 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 tanto, esta instancia tiene valor 3/4.
El valor de una instancia de portada de etiqueta única es la fracción de restricciones que se puede satisfacer con cualquier asignación. Para casos satisfactorios, este valor es 1 y es fácil de encontrar. Por otro lado, parece muy difícil determinar el valor de un juego insatisfactorio, incluso aproximadamente. La conjetura de los juegos únicos formaliza esta dificultad.
Más formalmente, el problema de la cubierta de la etiqueta ( c , s ) -gap con restricciones únicas es el siguiente problema de promesa ( L sí , L no ):
- L sí = { G : alguna asignación satisface al menos una fracción c de restricciones en G }
- L no = { G : Cada asignación satisface como máximo una fracción s de restricciones en G }
donde G es una instancia del problema de la cubierta de la etiqueta con restricciones únicas.
La conjetura de los juegos únicos establece que para cada par suficientemente pequeño de constantes ε , δ > 0, existe una constante k tal que el problema de cubierta de etiqueta (1 - δ , ε ) -gap con restricciones únicas sobre el alfabeto de tamaño k es NP -duro .
En lugar de gráficos, el problema de la cubierta de la etiqueta se puede formular en términos de ecuaciones lineales. Por ejemplo, supongamos que tenemos un sistema de ecuaciones lineales sobre los enteros módulo 7:
Este es un ejemplo del problema de la cubierta de la etiqueta 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.
Sistemas a prueba de dos probadores
Un juego único es un caso especial de un juego de una ronda de dos probadores (2P1R) . Un juego de una ronda de 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 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 satisface con sus preguntas y sus respuestas.
Un juego de una ronda de dos probadores 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 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 probabilísticamente comprobables
Alternativamente, la conjetura de juegos únicos postula la existencia de un cierto tipo de prueba probabilísticamente verificable para problemas en NP .
Un juego único puede verse como un tipo especial de prueba comprobable 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 establece que por cada par suficientemente pequeño de constantes ε , δ > 0 hay una constante K tal que cada problema en NP tiene una prueba probabilísticamente verificable sobre un alfabeto de tamaño K con completitud 1 - δ , solidez ε y aleatoriedad complejidad O (log ( n )) que es un juego único.
Relevancia
Problema | Tiempo polivinílico aprox. | Dureza NP | Dureza UG |
---|---|---|---|
Máx 2 sábados | 0,940 ... [5] | 0,954 ... + ε [6] | 0,9439 ... + ε [7] |
Corte máximo | 0,878 ... [8] | 0,941 ... + ε [6] | 0,878 ... + ε [7] |
Min Vertex Cover | 2 | 1.360 ... - ε [9] | 2- ε [10] |
Intermediación | 1/3 | 47/48 [11] | 1/3 + ε [12] |
Algunas declaraciones muy naturales e intrínsecamente interesantes sobre cosas como la votación y las espumas surgieron al estudiar el UGC ... Incluso si el UGC resulta ser falso, ha inspirado mucha investigación matemática interesante.
- Ryan O'Donnell, [1]
La conjetura de los juegos únicos fue introducida por Subhash Khot en 2002 para avanzar en ciertas cuestiones de la teoría de la dureza de aproximación .
La verdad de la conjetura de juegos únicos implicaría la optimalidad de muchos algoritmos de aproximación conocidos (asumiendo 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 gráfico es óptima dentro de cualquier constante aditiva asumiendo la conjetura de 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 c + ε o c - ε significa que el resultado se mantiene para cada constante (con respecto al tamaño del problema) estrictamente mayor o menor que c , respectivamente.
Discusión y alternativas
Actualmente, no hay consenso con respecto a la verdad de la conjetura de los juegos únicos. Se han refutado algunas 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 1 - δ del caso en el que el valor es como máximo ε es imposible para los algoritmos de tiempo polinómico (pero quizás no NP-hard). Esta forma de conjetura todavía sería útil para aplicaciones en dureza de aproximación.
La constante δ> 0 en las formulaciones anteriores de la conjetura es necesaria a menos que P = NP . Si se elimina el requisito de unicidad , el teorema de la repetición paralela sabe que el enunciado correspondiente es verdadero , incluso cuando δ = 0.
Marek Karpinski y Warren Schudy [13] construyeron esquemas de aproximación de tiempo lineal para casos densos de problemas de juegos únicos.
En 2008, Prasad Raghavendra demostró que si el UGC es verdadero, entonces para cada problema de satisfacción de restricciones (CSP) la mejor relación de aproximación viene dada por una cierta instancia de programación semidefinida simple (SDP), que es en particular polinomio [1] .
En 2010, Prasad Raghavendra y David Steurer definieron el problema "Expansión de espacios pequeños y pequeños" y conjeturaron que es NP-difícil. Esta conjetura implica la conjetura de juegos únicos. [14] También se ha utilizado para demostrar una gran dureza de los resultados de aproximación para encontrar subgrafos bipartitos completos . [15]
En 2010, Sanjeev Arora , Boaz Barak y David Steurer encontraron un algoritmo de aproximación temporal subexponencial para el problema de los juegos únicos. [dieciséis]
En 2012, se demostró que distinguir instancias con valor como máximo 3/8 + δ de instancias con valor al menos 1/2 se sabe que es NP-difícil. [17]
En 2018, después de una serie de artículos, se probó una versión más débil de la conjetura, llamada conjetura de juegos 2-2. En cierto sentido, esto prueba "la mitad" de la conjetura original [2] , [3] . Esto también mejora el espacio más conocido para la cubierta de etiqueta única: es NP-difícil distinguir instancias con valor como máximo δ de instancias con valor al menos 1/2. [18]
Notas
- ↑ a b c Erica Klarreich (6 de octubre de 2011). "Aproximadamente difícil: la conjetura de los juegos únicos" . Fundación Simons . Consultado el 29 de octubre de 2012 .
- ^ Dick Lipton (5 de mayo de 2010). "Juegos únicos: una obra de tres actos" . Letra perdida de Gödel y P = NP . Consultado el 29 de octubre de 2012 .
- ^ Khot, Subhash (2002), "On the power of unique 2-prover 1-round games", Actas del trigésimo cuarto simposio anual de ACM sobre teoría de la computación , págs. 767–775, doi : 10.1145 / 509907.510017 , ISBN 1-58113-495-9, S2CID 207635974
- ^ La conjetura de juegos únicos es vacuosamente cierta si P = NP , ya que entonces todos los problemas en NP también serían NP -difíciles.
- ^ Feige, Uriel; Goemans, Michel X. (1995), "Aproximación del valor de dos sistemas de prueba, con aplicaciones a MAX 2SAT y MAX DICUT", Proc. 3rd Israel Symp. Teoría de la Computación y los Sistemas , IEEE Computer Society Press, págs. 182–189
- ^ a b Håstad, Johan (1999), "Some Optimal Inapproximability Results" , Journal of the ACM , 48 (4): 798–859, doi : 10.1145 / 502090.502098 , S2CID 5120748 .
- ^ a b Khot, Subhash ; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), "¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de dos variables?" (PDF) , SIAM Journal on Computing , 37 (1): 319–357, doi : 10.1137 / S0097539705447372
- ^ Goemans, Michel X .; Williamson, David P. (1995), "Algoritmos de aproximación mejorados para problemas máximos de corte y satisfacción mediante programación semidefinida", Journal of the ACM , 42 (6): 1115-1145, doi : 10.1145 / 227683.227684 , S2CID 15794408
- ^ Dinur, Irit ; Safra, Samuel (2005), "Sobre la dureza de aproximar la cubierta mínima de vértices" (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007 / annals.2005.162.439 , recuperado 2010-03-05 .
- ^ Khot, Subhash ; Regev, Oded (2003), "La cobertura del vértice puede ser difícil de aproximar dentro de 2 - ε ", Conferencia IEEE sobre Complejidad Computacional : 379–
- ^ Chor, Benny; Sudán, 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.
- ^ Charikar, Moisés ; Guruswami, Venkatesan ; Manokaran, Rajsekar (2009), "Cada CSP de permutación de arity 3 es resistente a la aproximación", 24a Conferencia Anual de IEEE sobre Complejidad Computacional , págs. 62–73, doi : 10.1109 / CCC.2009.29 , MR 2932455 , S2CID 257225.
- ^ Karpinski, Marek; Schudy, Warren (2009), "Esquemas de aproximación de tiempo lineal para el juego Gale-Berlekamp y problemas de minimización relacionados", Actas del cuadragésimo primer Simposio Anual de ACM sobre Teoría de la Computación : 313–322, arXiv : 0811.3244 , doi : 10.1145 / 1536414.1536458 , ISBN 9781605585062, S2CID 6117694
- ^ Raghavendra, Prasad; Steurer, David (2010), "Graph expansion and the unique games conjecture" (PDF) , STOC'10 — Actas del Simposio Internacional ACM 2010 sobre Teoría de la Computación , ACM, Nueva York, págs. 755–764, doi : 10.1145 /1806689.1806792 , MR 2.743.325 , S2CID 1601199
- ^ Manurangsi, Pasin (2017), "Inaproximabilidad de Biclique de borde máximo, Biclicuo máximo equilibrado y corte k mínimo de la hipótesis de expansión de conjunto pequeño", en Chatzigiannakis, Ioannis; Indyk, Piotr; Kuhn, Fabián; Muscholl, Anca (eds.), 44 ° Coloquio Internacional sobre Autómatas, Idiomas y Programación (ICALP 2017) , Leibniz International Proceedings in Informatics (LIPIcs), 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
- ^ Arora, Sanjeev ; Barak, Booz; Steurer, David (2015), "Algoritmos subexponenciales para juegos únicos y problemas relacionados", Revista de la ACM , 62 (5): Art. 42, 25, doi : 10.1145 / 2775105 , MR 3.424.199 , S2CID 622344. Anunciado previamente en FOCS 2010.
- ^ O'Donnell, Ryan; Wright, John (2012), "Un nuevo punto de dureza NP para juegos únicos", Actas del Simposio ACM sobre Teoría de la Computación de 2012 (STOC'12) , Nueva York: ACM, págs. 289-306, doi : 10.1145 /2213977.2214005 , MR 2.961.512 , S2CID 6737664.
- ^ Subhash, K .; Minzer, D .; Safra, M. (octubre de 2018). "Los conjuntos pseudoaleatorios en el gráfico de Grassmann tienen una expansión casi perfecta" . 59º Simposio Anual de IEEE 2018 sobre Fundamentos de las Ciencias de la Computación (FOCS) : 592–601. doi : 10.1109 / FOCS.2018.00062 .
Referencias
- Khot, Subhash (2010), "Sobre la conjetura de los juegos únicos", Proc. 25th IEEE Conference on Computational Complexity (PDF) , págs. 99-121, doi : 10.1109 / CCC.2010.19.