Conjetura del tiempo exponencial

La conjetura del tiempo exponencial es una suposición no comprobada sobre la complejidad computacional que fue formulada por Impagliazzo y Paturi [1] . La conjetura establece que 3-SAT (o cualquiera de los problemas NP-completos relacionados) no puede resolverse en tiempo subexponencial en el peor de los casos [2] . La validez de la conjetura del tiempo exponencial, si es cierta, implicaría que P ≠ NP , pero la conjetura es una declaración más fuerte. A partir del enunciado de la hipótesis, se puede demostrar que muchos problemas computacionales son equivalentes en complejidad en el sentido de que si uno de ellos tiene un algoritmo de tiempo exponencial, entonces todos tienen algoritmos de la misma complejidad.

Definición

La tarea k -SAT es la tarea de verificar si una expresión booleana en forma normal conjuntiva que tiene más de k variables por expresión (conjuntiva) se puede hacer verdadera asignando el valor de valores booleanos a las variables de la expresión. Para cualquier número entero , definimos un número real como el mínimo de números reales , para lo cual existe un algoritmo para resolver el problema k -SAT en el tiempo , donde n es el número de variables en este problema k -SAT. Entonces , dado que el problema 2-SAT se puede resolver en tiempo polinomial . La hipótesis del tiempo exponencial es la suposición de que para cualquier . Está claro que , por lo que la conjetura es equivalente a la suposición de que , la positividad de los números restantes se sigue automáticamente de la suposición. $k\geqslant 2$ ${\ Displaystyle s_ {k}}$ $\delta$ $O(2^{\delta n})$ ${\ estilo de visualización s_ {2} = 0}$ $k>2,s_{k}>0$ $s_{3}\leqslant s_{4}\leqslant \ldots$ $s_{3}>0$ ${\ Displaystyle s_ {k}}$

Algunas fuentes definen la conjetura del tiempo exponencial como una afirmación un poco más débil de que el 3-SAT no se puede resolver a tiempo . Si existe un algoritmo para resolver el problema 3-SAT en el tiempo , entonces está claro que será igual a cero. Sin embargo, esto es consistente con el conocimiento actual de que puede haber una secuencia de algoritmos 3-SAT, cada uno ejecutándose en el tiempo para números que tienden a cero, pero la descripción de estos algoritmos crece rápidamente de tal manera que un solo algoritmo no puede seleccionar y ejecutar automáticamente el algoritmo más apropiado [3] . ${\ estilo de visualización 2 ^ {o (n)}}$ ${\ estilo de visualización 2 ^ {o (n)}}$ ${\ estilo de visualización s_ {3))$ ${\ estilo de visualización O (2 ^ {\ delta _ {i} n})}$ $\delta _{i}$

Dado que los números forman una secuencia monótona , que está acotada superiormente por uno, deben converger hasta el límite . La conjetura del tiempo exponencial fuerte (SETH) es la suposición de que el valor límite s ∞ de una secuencia de números s k es igual a uno [4] . $s_{3},s_{4},\ldots$ ${\displaystyle s_{\infty ))$

Otra versión de la conjetura es la conjetura del tiempo exponencial heterogéneo , que fortalece la segunda parte de ETH, que postula que no existe una familia de algoritmos (uno para cada longitud de entrada en el espíritu de sugerencia ) que pueda resolver el 3- Problema del SAT en el tiempo 2 o( n ) .

Corolario de satisfacción

No puede ser igual para ningún k finito ; como han demostrado Impagliazzo, Paturi y Zane [5] , existe una constante tal que . Por lo tanto, si la hipótesis del tiempo exponencial es cierta, debe haber infinitos valores de k para los cuales s k difiere de . ${\ Displaystyle s_ {k}}$ ${\displaystyle s_{\infty ))$ $\alfa$ $s_{k}\leqslant s_{\infty}(1-\alpha /k)$ $s_{k+1}$

Una herramienta importante en esta área es el lema de dispersión de Impagliazzo, Paturi y Zane [5] , que muestra que cualquier fórmula k -CNF puede ser reemplazada por fórmulas k -CNF más simples en las que cada variable aparece solo un número constante de veces, por lo que el número de oraciones es lineal. El lema de la escasez se prueba encontrando sucesivamente grandes conjuntos de expresiones que tienen una intersección común no vacía en una fórmula dada, y reemplazando la fórmula con dos fórmulas más simples, en una de las cuales cada expresión se reemplaza por su intersección común, y en la otra intersección se elimina de cada expresión. Al aplicar el lema disperso y usar nuevas variables para dividir expresiones, se puede obtener un conjunto de fórmulas de 3-CNF, cada una con un número lineal de variables, de modo que la fórmula original de k - CNF es satisfactoria si y solo si al menos una de estas fórmulas de 3-CNF son factibles. Por lo tanto, si el 3-SAT se pudo resolver en un tiempo subexponencial, se puede usar esta reducción para resolver el problema k - SAT en un tiempo subexponencial. De manera equivalente, si para cualquier k > 3, entonces la conjetura del tiempo exponencial también es cierta [2] [5] . $\epsilon > 0$ ${\ estilo de visualización O (2 ^ {{\ épsilon} n})}$ ${\ estilo de visualización O (2 ^ {\ épsilon} n)}$ $s_{k}>0$ $s_{3}>0$

El valor límite de la sucesión de números s k no excede de s CNF , donde s CNF es el mínimo de números tales que la satisfacibilidad de fórmulas en forma conjuntiva normal sin limitar la longitud de la expresión puede resolverse en el tiempo . Por lo tanto, si la conjetura del tiempo exponencial fuerte es verdadera, entonces no hay ningún algoritmo para el problema general de satisfacibilidad CNF que sea sustancialmente más rápido que probar la verdad de todas las proposiciones posibles . Sin embargo, si la fuerte conjetura sobre el tiempo exponencial no es cierta, sigue siendo posible que s CNF sea igual a uno [6] . ${\displaystyle s_{\infty ))$ $\delta$ $O(2:{{\delta }n})$

Consecuencias de los problemas de búsqueda

La conjetura del tiempo exponencial implica que muchos otros problemas en la clase de complejidad SNP no tienen algoritmos cuyo tiempo de ejecución sea menor que c n para alguna constante c . Estos problemas incluyen la capacidad de coloración de gráficos k , encontrar ciclos hamiltonianos , camarillas más grandes , conjuntos independientes más grandes y coberturas de vértices en gráficos con n vértices. Por el contrario, si alguno de estos problemas tiene un algoritmo subexponencial, entonces será posible demostrar que la conjetura del tiempo exponencial es falsa [2] [5] .

Si se pudieran encontrar camarillas o conjuntos independientes de tamaño logarítmico en tiempo polinomial, la conjetura de tiempo exponencial sería incorrecta. Por lo tanto, incluso si es poco probable que encontrar camarillas o conjuntos independientes de un tamaño tan pequeño sea NP-completo, la conjetura del tiempo exponencial implica que estos problemas no son polinómicos [2] [7] . De manera más general, la conjetura del tiempo exponencial implica que es imposible encontrar camarillas o conjuntos independientes de tamaño k en el tiempo [8] . La hipótesis del tiempo exponencial también implica que es imposible resolver el problema k -SUM (dados n números reales, necesitas encontrar k de ellos, dando la suma cero) en el tiempo . La conjetura del tiempo exponencial fuerte implica que es imposible encontrar conjuntos dominantes que consisten en k vértices en menos de tiempo [6] . $n^{o(k)}$ $n^{o(k)}$ ${\ Displaystyle n^{ko(1)}}$

También se deduce de la hipótesis del tiempo exponencial que el problema ponderado de encontrar un conjunto de arcos de corte de ciclo en torneos (FAST) no tiene un algoritmo paramétrico con tiempo de ejecución , ni siquiera tiene un algoritmo paramétrico con tiempo de ejecución [9] . $O^{*}(2^{o({\sqrt {OPT)))})$ $O^{*}(2^{O({\sqrt {OPT)))})$

La fuerte conjetura del tiempo exponencial conduce a límites definidos en la complejidad parametrizada de algunos problemas en gráficos con un ancho de árbol acotado . En particular, si la conjetura del tiempo exponencial fuerte es cierta, entonces el límite de tiempo óptimo para encontrar conjuntos independientes en gráficos con un ancho de eswárbol [10] . De manera equivalente, cualquier mejora en estos tiempos de ejecución invalidaría la fuerte conjetura del tiempo exponencial [11] . También se deduce de la hipótesis del tiempo exponencial que cualquier algoritmo fijo paramétricamente decidible para cubrir los bordes de un gráfico con camarillas debe tener una doble dependencia exponencial del parámetro [12] . ${\ estilo de visualización (2o (1)) ^ {w} n ^ {O (1)}}$ ${\displaystyle (3-o(1))^{w}n^{O(1)))$ ${\ estilo de visualización (2-o (1)) ^ {w} n ^ {O (1)))$ ${\ estilo de visualización (ko (1)) ^ {w} n ^ {O (1)}}$

Implicaciones en la teoría de la complejidad de la comunicación

En el problema de la disyunción tripartita de conjuntos en la complejidad de la comunicación, se dan tres subconjuntos de números enteros de algún intervalo [1, m ] y se dan tres participantes comunicantes, cada uno de los cuales conoce dos de los tres subconjuntos. El objetivo de los participantes es transferir la menor cantidad posible de información entre sí a través de un canal de comunicación común, pero para que uno de los participantes pueda determinar si la intersección de los tres conjuntos está vacía o no. Un protocolo trivial de m bits sería enviar a uno de los participantes del vector de bits que describe la intersección de dos conjuntos conocidos por él, después de lo cual cada uno de los dos participantes restantes puede determinar el vacío de la intersección. Sin embargo, si hay un protocolo que resuelve el problema en o( m ) saltos y cálculos, se puede convertir a un algoritmo k -SAT en O(1.74 n ) tiempo para cualquier constante k fija , lo que viola la hipótesis del tiempo exponencial fuerte . Por lo tanto, de la fuerte conjetura sobre el tiempo exponencial se deduce que, o bien el protocolo trivial para el problema de la disyuntividad tripartita de conjuntos es óptimo, o cualquier protocolo mejor requiere un número exponencial de cálculos [6] . ${\ estilo de visualización 2 ^ {o (m)}}$

Consecuencias en la teoría de la complejidad estructural

Si la hipótesis del tiempo exponencial es correcta, entonces 3-SAT no debería tener un algoritmo de tiempo polinomial, por lo que se seguiría que P ≠ NP . Más fuertemente, en este caso el problema 3-SAT ni siquiera tendría un algoritmo de tiempo cuasi-polinomial , por lo que NP no podría ser un subconjunto de la clase QP. Sin embargo, si la conjetura del tiempo exponencial no es cierta, no se seguiría que las clases P y NP son iguales. Hay problemas NP-completos para los cuales el mejor tiempo de solución conocido es de la forma , y si el mejor tiempo de ejecución posible para el 3-SAT fuera de esta forma, entonces P no sería igual a NP (porque 3-SAT es un problema NP-completo, y este tiempo no es polinomial), pero la conjetura del tiempo exponencial sería incorrecta. $O(2^{n^{c)))$ ${\ estilo de visualización c <1}$

En la teoría de la complejidad paramétrica, dado que la hipótesis del tiempo exponencial implica que no existe un algoritmo decidible paramétricamente fijo para encontrar la camarilla más grande, también implica que W[1] ≠ FPT [8] . ¿Es un problema abierto importante en esta área? ¿Se puede revertir este corolario ? ¿Se sigue la conjetura del tiempo exponencial? Existe una jerarquía de clases de complejidad paramétrica denominada jerarquía M, que se intercala con la jerarquía W en el sentido de que para todo i , . Por ejemplo, el problema de encontrar una cobertura de vértices de un tamaño en un grafo con n vértices es completo para M[1]. La conjetura sobre el tiempo exponencial es equivalente a la afirmación de que , y la cuestión de la igualdad para i > 1 también permanece abierta [3] . $W[1]\neq FPT$ $M[i]\subseteq W[i]\subseteq M[i+1]$ $k\log(n)$ $M[1]\neq FPT$ $METRO[i]=W[i]$

También se puede mostrar la derivación en la otra dirección, desde el fracaso de la conjetura fuerte sobre el tiempo exponencial hasta clases de complejidad separadas. Como demostró Williams [13] , si existe un algoritmo A que resuelve el problema booleano de satisfacibilidad del tiempo para alguna función de crecimiento superpolinomial , entonces NEXPTIME no es un subconjunto de P/poly . Williams demostró que si existe el Algoritmo A y también existe una familia de esquemas que simulan NEXPTIME en P/poly, entonces el Algoritmo A podría combinarse con un esquema para modelar tareas NEXPTIME de forma no determinista en menos tiempo, lo que contradice el Teorema de la Jerarquía del Tiempo . Así, la existencia del Algoritmo A prueba la imposibilidad de la existencia de una familia de circuitos y la separación de estas dos clases de complejidad. ${\ estilo de visualización 2^{n}/f(n)}$ $F$

Notas

↑ Impagliazzo, Paturi, 1999 .
↑ 1 2 3 4 Woeginger, 2003 .
↑ 1 2 Flum, Grohe, 2006 .
↑ Dantsin, Wolpert, 2010 .
↑ 1 2 3 4 Impagliazzo, Paturi, Zane, 2001 .
↑ 1 2 3 Pătraşcu, Williams, 2010 .
↑ Feige, Kilian, 1997 .
↑ 1 2 Chen, Huang, Kanj, Xia, 2006 .
↑ Karpinski, Warren, 2010 .
↑ Cygan, Fomin, Kowalik, Lokshtanov y otros, 2015 .
↑ Lokshtanov, Marx, Saurabh, 2011 .
↑ Cygan, Pilipczuk, Pilipczuk, 2013 .
↑ Williams, 2010 .

Literatura

Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia. Fuertes límites inferiores computacionales a través de la complejidad parametrizada // Journal of Computer and System Sciences. - 2006. - T. 72 , núm. 8 _ - S. 1346-1367 . -doi : 10.1016/ j.jcss.2006.04.007 .
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh. Algoritmos parametrizados. - Springer, 2015. - Pág. 555. - ISBN 978-3-319-21274-6 .
Marek Cygan, Marcin Pilipczuk, Michal Pilipczuk. Los algoritmos conocidos para EDGE CLIQUE COVER son probablemente óptimos // Proc. 24º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA 2013) . - 2013. Archivado el 16 de abril de 2013.
Evgeny Dantsin, Alexander Wolpert. Teoría y aplicaciones de las pruebas de satisfacción–SAT 2010. Springer-Verlag, 2010. Vol. 6175 . - S. 313-325 . -doi : 10.1007 / 978-3-642-14186-7_27 .
Uriel Feige , Joe Kilian. Sobre el no determinismo limitado versus polinomial // Ciencias de la Computación Teórica. - 1997. - vol. 1 . - P. 1-20 .
Jörg Flum, Martin Grohe. 16. Trazabilidad de parámetros fijos subexponenciales // Teoría de la complejidad parametrizada . - Springer-Verlag, 2006. - S. 417 -451. - (Textos de la EATCS en Informática Teórica). — ISBN 978-3-540-29952-3 .
Russel Impagliazzo, Ramamohan Paturi. La complejidad de k-SAT // Proc. 14ª Conferencia IEEE. sobre la Complejidad Computacional . - 1999. - S. 237-240. -doi : 10.1109/ CCC.1999.766282 .
Russel Impagliazzo, Ramamohan Paturi, Francis Zane. ¿Qué problemas tienen una complejidad fuertemente exponencial? // Revista de Ciencias de la Computación y Sistemas. - 2001. - T. 63 , núm. 4 . - S. 512-530 . -doi : 10.1006/ jcss.2001.1774 .
Marek Karpinski, Schudy Warren. Algoritmos más rápidos para el torneo Feedback Arc Set, la agregación de rangos de Kemeny y el torneo de intermediación // Proc. ISAAC 2010, Parte I. - 2010. - P. 3-14 . -doi : 10.1007 / 978-3-642-17517-6_3 .
Daniel Lokshtanov, Daniel Marx, Saket Saurabh. Los algoritmos conocidos en gráficos de ancho de árbol acotado son probablemente óptimos // Proc. 22º Simposio ACM/SIAM sobre algoritmos discretos (SODA 2011) . - 2011. - S. 777-789. Archivado el 18 de octubre de 2012 en Wayback Machine .
Mihai Patraşcu, Ryan Williams. Sobre la posibilidad de algoritmos SAT más rápidos // Proc. 21º Simposio ACM/SIAM sobre Algoritmos Discretos (SODA 2010) . - 2010. - S. 1065-1075.
Ryan Williams. Mejorar la búsqueda exhaustiva implica límites inferiores superpolinomiales // Proc. 42º Simposio ACM sobre Teoría de la Computación (STOC 2010). - Nueva York, NY, EE. UU.: ACM, 2010. - S. 231-240. -doi : 10.1145/ 1806689.1806723 .
Gerhard J. Woeginger. Algoritmos exactos para problemas NP-difíciles: Una encuesta // Optimización Combinatoria — ¡Eureka, You Shrink! . - Springer-Verlag, 2003. - T. 2570. - S. 185-207. -doi : 10.1007/ 3-540-36478-1_17 .