Conjetura del Juego Único
En teoría de la complejidad computacional, la Conjetura del Juego Único 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 de juego, conocido como un juego único, tiene complejidad algorítmica NP-hard. Tiene amplias aplicaciones en la teoría de la dureza de aproximación. Si esto es cierto, entonces para muchos problemas importantes no es sólo demasiado difícil conseguir una solución exacta (como postula el problema P contra NP), sino también muy difícil obtener una buena aproximación. Hay implicaciones importantes para problema de satisfacción de restricciones que surgen en una amplia variedad de disciplinas.
La conjetura es inusual y el mundo académico parece acerca uniformemente dividido sobre si es cierto o no.[1]
"Algunas declaraciones muy naturales, intrínsecamente interesantes sobre cosas como la votación y espumas sólo salieron al estudiar la CJU.... Incluso si la CJU resulta ser falsa, ha inspirado una gran cantidad de interesantes investigaciones matemáticas."Ryan O’Donnell[1]
Formulaciones editar
La conjetura de juegos únicos puede afirmar en un número de maneras equivalentes.
Cobertura de la etiqueta única editar
La siguiente formulación de la conjetura de juegos únicos se utiliza a menudo en la dureza de la aproximación. La conjetura postula la NP-hardness del siguiente problema promesa conocido como cobertura de las etiquetas a restricciones de unicidad. Para cada arista, los colores de los dos vértices están restringidos a algunos pares ordenados particulares. En particular, 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 la cubierta de etiqueta con restricciones únicas más de un alfabeto de tamaño k puede representarse como un grafo junto con una colección de permutacioness pe: [k] -> [k], una para cada arista e del grafo. Una asignación a una instancia de la cubierta etiqueta da a cada vértice de G un valor en el conjunto [k], a menudo llamados “colores”.
Tales casos están fuertemente limitados en el sentido de que el color de un vértice define de forma exclusiva 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, entonces tal 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 ser resuelto en tiempo polinomial.
El valor de una instancia de cubierta de etiqueta única es la fracción de las limitaciones que pueden ser satisfechas por cualquier asignación. Para las instancias que pueden ser satisfechas, el valor es 1 y es fácil de encontrar. Por otro lado, parece ser muy difícil determinar el valor de un juego insatisfacible, ni siquiera aproximadamente. La conjetura de juegos única formaliza esta dificultad.
Más formalmente, el problema de cobertura de etiqueta del intervalo (c, s) con restricciones de unicidad es el siguiente problema promesa (Lsi, Lno):
- Lsi = {G: Algunas asignaciones satisfacen al menos c-fracciones de limitaciones en G G}
- Lno = {G: Cada asignación satisface a lo sumo s-fracciones de las restricciones en G}
donde G es una instancia del problema de cobertura etiqueta con restricciones de unicidad.
Los juegos únicos conjeturan estados que por cada par suficientemente pequeño de constantes e, d> 0, existe una constante k tal que el problema de cobertura etiqueta en el intervalo (1 - d, e) con restricciones únicas sobre alfabeto de tamaño k es NP-hard.
En lugar de grafos, el problema de cobertura de la etiqueta se puede ser formulado en términos de ecuaciones lineales. Por ejemplo, supongamos que tenemos un sistema de ecuaciones lineales sobre los enteros módulo 7:
Esta es una instancia del problema de cobertura etiqueta a restricciones de unicidad. Por ejemplo, la primera ecuación corresponde a la permutación p(1, 2) where p(1, 2)(x1) = 2x2 módulo 7.
Sistemas de prueba de dos prover editar
Un juego único es un caso especial de dos prover una sola ronda (2P1R) juego. Una juego de dos prover de una sola ronda tiene dos jugadores (también conocidos como provers) y un árbitro. El árbitro envía a cada jugador una pregunta extraída de una distribución de probabilidad conocida, y los jugadores cada uno deberá 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 dadas 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.
Una juego de dos prover de una sola ronda se llama un juego único si para cada par de preguntas y todas las respuestas a la primera pregunta, hay exactamente una respuesta a la segunda pregunta que se traduce en una victoria para los jugadores, y viceversa. El valor de un juego es la probabilidad máximo de ganar para los jugadores a través de todas las estrategias.
Los juegos únicos conjeturan estados que por cada par suficientemente pequeño de constantes e,, d > 0,, existe una constante k tal que el siguiente problema promesa (Lyes, Lno) (Lsi, Lno) es NP-hard:
- Lsi = {G: el valor de G es al menos 1 − d}
- Lno = {G: el valor de G es a lo sumo e}
donde G es un juego único cuyas respuestas provienen de un conjunto de tamaño k.
Pruebas probabilísticamente comprobables editar
Alternativamente, la conjetura de juegos único postula la existencia de un cierto tipo de pruebas probabilísticamente comprobables para problemas en NP.
Un juego único puede ser visto como un tipo especial de prueba no adaptativa probabilísticamente comprobable con la 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.
Los juegos únicos conjeturan estados que por cada par suficientemente pequeño de constantes e, d> 0 existe una constante K tal que todo problema en NP tiene una prueba probabilísticamente comprobable sobre un alfabeto de tamaño K con completitud 1 - d, e solidez y complejidad de aleatoriedad O (log (n)) lo cual es un juego único.
Relevancia editar
| Problema | Polinomial(tiempo aprox.) | NP | UG |
|---|---|---|---|
| Max 2-Sat | 0.940.[4] | 0.954...+e[5] | 0.940...+e[6] |
| Max Cut | 0.878.[7] | 0.941...+e[5] | 0.878...+e[6] |
| Min Vertex Cover | 2 | 1.360...-e[8] | 2-e[9] |
La conjetura de juegos únicos fue introducido por Subhash Khot en 2002 con el fin de avanzar en algunas cuestiones en 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 (suponiendo que P ≠ NP).Por ejemplo, la relación de aproximación alcanzado por el algoritmo de Goemans and Williamson para aproximar el corte máximo en un grafo es óptimo dentro de cualquier constante aditiva asumiendo la conjetura de juegos únicos y P ≠ NP.
Una lista de resultados conocidos de la conjetura de juegos único se muestra en la tabla a la derecha junto con los correspondientes mejores resultados para la débil suposición de P ≠ NP. Una constante de c+e or c-e significa que el resultado es válido para cada constante (con respecto al tamaño del problema) estrictamente mayor que o menor que c, respectivamente.
Discusión y alternativas editar
Actualmente no existe un consenso en cuanto a la certeza de la conjetura de juegos único. Ciertas formas más fuertes de la conjetura han sido refutadas.
Una forma diferente de la conjetura postula que distinguir el caso cuando el valor de un juego único es al menos 1 − d de cuando el valor es como máximo e es imposible para los algoritmos en tiempo polinómico (pero tal vez no NP-hard). Esta forma de la conjetura todavía sería útil para aplicaciones en la dureza de la aproximación.
La constante d > 0 en las formulaciones anteriores de la conjetura es necesario a menos que P = NP. Si se elimina el requisito de singularidad la declaración correspondiente se sabe que es cierto por el teorema de repetición paralelo, incluso cuando d = 0.
En 2010, Arora, Barak y Steurer encontraron un algoritmo de aproximación de tiempo subexponencial para problemas de juegos únicos.[10]
Notas editar
- ↑ a b c Erica Klarreich (6 de octubre de 2011). «Approximately Hard: The Unique Games Conjecture». Simons Foundation. Archivado desde el original el 14 de octubre de 2012. Consultado el 29 de octubre de 2012.
- ↑ Dick Lipton (5 de mayo de 2010). «Unique Games: A Three Act Play». Gödel’s Lost Letter and P=NP. Consultado el 29 de octubre de 2012.
- ↑ Khot, Subhash (2002), «On the power of unique 2-prover 1-round games», Proceedings of the thirty-fourth annual ACM symposium on Theory of computing, pp. 767-775, ISBN 1-58113-495-9, doi:10.1145/509907.510017.
- ↑ Feige, Uriel; Goemans, Michel X. (1995), «Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT», Proc. 3rd Israel Symp. Theory of Computing and Systems, IEEE Computer Society Press, pp. 182-189.
- ↑ a b Håstad, Johan (1999), «Some Optimal Inapproximability Results», Journal of the ACM..
- ↑ a b Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007), «Optimal inapproximability results for MAX-CUT and other two-variable CSPs?», SIAM Journal on Computing 37 (1): 319-357, doi:10.1137/S0097539705447372.
- ↑ Goemans, Michel X.; Williamson, David P. (1995), «Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming», Journal of the ACM.
- ↑ Dinur, Irit; Safra, Samuel (2005), «On the hardness of approximating minimum vertex cover», Annals of Mathematics 162 (1): 439-485, doi:10.4007/annals.2005.162.439, archivado desde el original el 20 de septiembre de 2009, consultado el 5 de marzo de 2010..
- ↑ Khot, Subhash; Regev, Oded (2003), «Vertex cover might be hard to approximate to within 2-e», IEEE Conference on Computational Complexity: 379-.
- ↑ «Subexponential Algorithms for Unique Games and Related Problems». Archivado desde el original el 5 de septiembre de 2012. Consultado el 5 de diciembre de 2014.
Referencias editar
- Khot, Subhash (2010), «On the Unique Games Conjecture», Proc. 25th IEEE Conference on Computational Complexity, pp. 99-121, doi:10.1109/CCC.2010.19..
Datos: Q7886950
