En la teoría de la complejidad computacional , la hipótesis del tiempo exponencial es una suposición de dureza computacional no probada que fue formulada por Impagliazzo y Paturi (1999) . La hipótesis establece que 3-SAT (o cualquiera de varios, pero no todos, [1] problemas NP-completos ) no se puede resolver en tiempo subexponencial en el peor de los casos . [2] La hipótesis del tiempo exponencial, si es cierta, implicaría que P ≠ NP, pero es una declaración más fuerte. Puede usarse para mostrar que muchos problemas computacionales son equivalentes en complejidad, en el sentido de que si uno de ellos tiene un algoritmo de tiempo subexponencial, entonces todos lo tienen.
Definición
k -SAT es el problema de probar si una expresión booleana , en forma normal conjuntiva con un máximo de k variables por cláusula, puede hacerse verdadera mediante alguna asignación de valores booleanos a sus variables. Para cada entero k ≥ 2, defina un número real s k como el mínimo de los números reales δ para los cuales k -SAT puede resolverse algorítmicamente en el tiempo O (2 δ n ), donde n es el número de variables en el k -instancia SAT. Entonces s 2 = 0, porque 2-SAT se puede resolver en tiempo polinomial . Además, s 3 ≤ s 4 ≤ ..., ya que la dificultad no disminuye con el crecimiento de k .
La hipótesis del tiempo exponencial es la conjetura de que s k > 0 para todo k > 2 o, de manera equivalente, que s 3 > 0.
Algunas fuentes definen la hipótesis del tiempo exponencial como la afirmación ligeramente más débil de que el 3-SAT no se puede resolver en el tiempo 2 o ( n ) . Si existiera un algoritmo para resolver 3-SAT en el tiempo 2 o ( n ) , entonces s 3 sería igual a cero. Sin embargo, es consistente con el conocimiento actual que podría haber una secuencia de algoritmos 3-SAT, cada uno con tiempo de ejecución O (2 δ i n ) para una secuencia de números δ i tendiendo hacia cero, pero donde las descripciones de estos algoritmos son creciendo tan rápidamente que un solo algoritmo no podría seleccionar y ejecutar automáticamente el más apropiado. [3]
Debido a que los números s 3 , s 4 , ... forman una secuencia monótona que está acotada arriba por uno, deben converger a un límite s ∞ . La hipótesis del tiempo exponencial fuerte (SETH) es la conjetura de que s ∞ = 1. [4]
Otra variante es la hipótesis del tiempo exponencial no uniforme , un fortalecimiento de la segunda redacción de la ETH, que postula que no existe una familia de algoritmos (uno para cada longitud de la entrada, en el espíritu de consejo ) que pueda resolver 3- SAT en el tiempo 2 o ( n ) .
Implicaciones para la satisfacibilidad
No es posible que s k sea igual a s ∞ para cualquier k finito : como demostraron Impagliazzo, Paturi y Zane (2001) , existe una constante α tal que s k ≤ s ∞ (1 - α / k ). Por lo tanto, si la hipótesis del tiempo exponencial es cierta, debe haber un número infinito de valores de k para los cuales s k difiere de s k + 1 .
Una herramienta importante en esta área es el lema de dispersión de Impagliazzo, Paturi y Zane (2001) , que muestra que, para cualquier ε > 0, cualquier fórmula k -CNF puede ser reemplazada por fórmulas O (2 εn ) más simples k -CNF en en el que cada variable aparece solo un número constante de veces, y por lo tanto en el que el número de cláusulas es lineal. El lema de esparcimiento se prueba encontrando repetidamente grandes conjuntos de cláusulas que tienen una intersección común no vacía en una fórmula dada, y reemplazando la fórmula por dos fórmulas más simples, una de las cuales tiene cada una de estas cláusulas reemplazada por su intersección común y la otra de las cuales tiene la intersección eliminada de cada cláusula. Al aplicar el lema de dispersión y luego usar nuevas variables para dividir las cláusulas, se puede obtener un conjunto de fórmulas O (2 εn ) 3-CNF, cada una con un número lineal de variables, de modo que la fórmula k -CNF original sea satisfactoria si y solo si al menos una de estas fórmulas 3-CNF es satisfactoria. Por lo tanto, si el 3-SAT pudiera resolverse en tiempo subexponencial, se podría usar esta reducción para resolver k -SAT también en tiempo subexponencial. De manera equivalente, si s k > 0 para cualquier k > 3, entonces s 3 > 0 también, y la hipótesis del tiempo exponencial sería cierta. [2] [5]
El valor límite s ∞ de la secuencia de números s k es como máximo igual a s CNF , donde es CNF es el ínfimo de los números delta tal que satisfacibilidad de fórmulas forma normal conjuntiva sin límites de longitud cláusula puede ser resuelto en el tiempo O (2 δn ). Por lo tanto, si la hipótesis del tiempo exponencial fuerte es cierta, entonces no habría ningún algoritmo para la satisfacibilidad general de CNF que sea significativamente más rápido que probar todas las posibles asignaciones de verdad . Sin embargo, si falla la hipótesis del tiempo exponencial fuerte, aún sería posible que s CNF sea igual a uno. [6]
Implicaciones para otros problemas de búsqueda
La hipótesis del tiempo exponencial implica que muchos otros problemas en la clase de complejidad SNP no tienen algoritmos cuyo tiempo de ejecución sea más rápido que c n para alguna constante c . Estos problemas incluyen gráfico k -colorability , la búsqueda de ciclos hamiltonianos , camarillas máximas , conjuntos máximos independientes , y cubierta de vértice en n gráficos -vertex. Por el contrario, si alguno de estos problemas tiene un algoritmo subexponencial, entonces se podría demostrar que la hipótesis del tiempo exponencial es falsa. [2] [5]
Si se pudieran encontrar camarillas o conjuntos independientes de tamaño logarítmico en tiempo polinomial, la hipótesis del tiempo exponencial sería falsa. Por lo tanto, aunque es poco probable que encontrar camarillas o conjuntos independientes de tamaño tan pequeño sea NP-completo, la hipótesis del tiempo exponencial implica que estos problemas no son polinomiales. [2] [7] De manera más general, la hipótesis del tiempo exponencial implica que no es posible encontrar camarillas o conjuntos independientes de tamaño k en el tiempo n o ( k ) . [8] La hipótesis del tiempo exponencial también implica que no es posible resolver el problema k -SUM (dados n números reales, encuentre k de ellos que sumen cero) en el tiempo n o ( k ) . La hipótesis del tiempo exponencial fuerte implica que no es posible encontrar conjuntos dominantes del vértice k más rápidamente que en el tiempo n k - o (1) . [6]
La hipótesis del tiempo exponencial implica también que el problema del Torneo de conjunto de arco de retroalimentación ponderado (FAST) no tiene un algoritmo parametrizado con tiempo de ejecución O * (2 o ( √ OPT ) ), sí tiene un algoritmo parametrizado con tiempo de ejecución O * ( 2 O ( √ OPT ) ). [9]
La hipótesis del tiempo exponencial fuerte conduce a límites estrechos en la complejidad parametrizada de varios problemas de gráficos en gráficos de ancho de árbol acotado . En particular, si la hipótesis del tiempo exponencial fuerte es cierta, entonces el límite de tiempo óptimo para encontrar conjuntos independientes en gráficas de ancho de árbol w es (2 - o (1)) w n O (1) , el tiempo óptimo para el problema de conjuntos dominantes es (3 - o (1)) w n O (1) , el tiempo óptimo para el corte máximo es (2 - o (1)) w n O (1) , y el tiempo óptimo para k- colorear es ( k - o (1)) w n O (1) . [10] De manera equivalente, cualquier mejora en estos tiempos de ejecución falsearía la hipótesis del tiempo exponencial fuerte. [11] La hipótesis del tiempo exponencial también implica que cualquier algoritmo manejable de parámetro fijo para la cobertura de la camarilla de borde debe tener una dependencia exponencial doble del parámetro. [12]
Implicaciones en la complejidad de la comunicación
En el problema de la disyunción de conjuntos tripartitos en la complejidad de la comunicación , se especifican tres subconjuntos de números enteros en algún rango [1, m ], y tres partes comunicantes conocen cada uno dos de los tres subconjuntos. El objetivo es que las partes se transmitan unos pocos bits entre sí en un canal de comunicaciones compartido para que una de las partes pueda determinar si la intersección de los tres conjuntos está vacía o no. Un protocolo de comunicaciones trivial de m bits sería que una de las tres partes transmita un vector de bits que describa la intersección de los dos conjuntos conocidos por esa parte, después de lo cual cualquiera de las dos partes restantes puede determinar el vacío de la intersección. Sin embargo, si existe un protocolo que resuelve el problema con o ( m ) la comunicación y 2 o ( m ) de cálculo, que podrían transformarse en un algoritmo para resolver k -SAT en tiempo O (1,74 n ) para cualquier constante fijo k , violando la hipótesis del tiempo exponencial fuerte. Por lo tanto, la hipótesis del tiempo exponencial fuerte implica que el protocolo trivial para la disyunción de conjuntos de tres partes es óptimo o que cualquier protocolo mejor requiere una cantidad exponencial de cálculo. [6]
Implicaciones en la complejidad estructural
Si la hipótesis del tiempo exponencial es cierta, entonces 3-SAT no tendría un algoritmo de tiempo polinomial y, por lo tanto, se seguiría que P ≠ NP . Más fuertemente, en este caso, 3-SAT ni siquiera podría tener un algoritmo de tiempo cuasi-polinomial , por lo que NP no podría ser un subconjunto de QP. Sin embargo, si la hipótesis del tiempo exponencial falla, no tendría implicaciones para el problema P versus NP. Existen problemas NP-completos para los cuales los tiempos de ejecución más conocidos tienen la forma O (2 n c ) para c <1, y si el mejor tiempo de ejecución posible para 3-SAT fuera de esta forma, entonces P sería diferente a NP (porque 3-SAT es NP-completo y este límite de tiempo no es polinomio) pero la hipótesis del tiempo exponencial sería falsa.
En la teoría de la complejidad parametrizada, debido a que la hipótesis del tiempo exponencial implica que no existe un algoritmo manejable con parámetros fijos para la camarilla máxima, también implica que W [1] ≠ FPT . [8] Es un problema abierto importante en esta área si esta implicación puede revertirse: ¿ W [1] ≠ FPT implica la hipótesis del tiempo exponencial? Existe una jerarquía de clases de complejidad parametrizadas llamada jerarquía M que entrelaza la jerarquía W en el sentido de que, para todo i , M [ i ] ⊆ W [ i ] ⊆ M [ i + 1] ; por ejemplo, el problema de encontrar una cobertura de vértices de tamaño k log n en un gráfico de n -vértices con parámetro k es completo para M [1]. La hipótesis del tiempo exponencial es equivalente a la afirmación de que M [1] ≠ FPT , y la cuestión de si M [ i ] = W [ i ] para i > 1 también está abierta. [3]
También es posible probar implicaciones en la otra dirección, desde el fracaso de una variación de la hipótesis del tiempo exponencial fuerte hasta las separaciones de clases de complejidad. Como muestra Williams (2010) , si existe un algoritmo A que resuelve la satisfacibilidad del circuito booleano en el tiempo 2 n / ƒ ( n ) para alguna función de crecimiento superpolinómico ƒ, entonces NEXPTIME no es un subconjunto de P / poli . Williams muestra que, si existe el algoritmo A , y también existió una familia de circuitos que simulan NEXPTIME en P / poly, entonces el algoritmo A podría componerse con los circuitos para simular problemas NEXPTIME de forma no determinista en una menor cantidad de tiempo, violando el teorema de la jerarquía temporal . Por tanto, la existencia del algoritmo A prueba la inexistencia de la familia de circuitos y la separación de estas dos clases de complejidad.
Ver también
- El teorema de Savitch , que muestra que una brecha exponencial similar no puede ser válida para la complejidad del espacio.
Notas
- ^ Por ejemplo, el problema de conjunto independiente máximo para gráficas planas es NP-completo, pero se puede resolver en tiempo subexponencial. Cuando una instancia de 3-SAT de tamaño n se reduce a un problema de MIS plano, el tamaño de este último crece a un orden de Θ ( n 2 ), por lo que un límite inferior exponencial para 3-SAT se traduce en un límite inferior que es subexponencial en el tamaño de instancia expandido.
- ↑ a b c d Woeginger (2003) .
- ↑ a b Flum y Grohe (2006) .
- ^ Calabro, Impagliazzo y Paturi (2009) .
- ↑ a b Impagliazzo, Paturi y Zane (2001) .
- ↑ a b c Pătraşcu y Williams (2010) .
- ^ Feige y Kilian (1997) .
- ^ a b Chen y col. (2006) .
- ^ Karpinski y Schudy (2010)
- ^ Cygan y col. (2015)
- ^ Lokshtanov, Marx y Saurabh (2011) .
- ^ Cygan, Pilipczuk y Pilipczuk (2013) .
Referencias
- Calabro, Chris; Impagliazzo, Russel ; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits", Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhague, Dinamarca, 10-11 de septiembre de 2009, Revised Selected Papers , págs. 75–85.
- Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A .; Xia, Ge (2006), "Límites inferiores computacionales fuertes a través de la complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346-1367, doi : 10.1016 / j.jcss.2006.04.007.
- Cygan, Marek; Fomin, Fedor V .; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Algoritmos parametrizados , Springer, p. 555, ISBN 978-3-319-21274-6
- Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), "Los algoritmos conocidos para EDGE CLIQUE COVER son probablemente óptimos", Proc. 24th ACM-SIAM Symposium on Discrete Algorithms (SODA 2013) , arXiv : 1203.1754 , Bibcode : 2012arXiv1203.1754C , archivado desde el original el 16 de abril de 2013.
- Dantsin, Evgeny; Wolpert, Alexander (2010), "Sobre tiempo moderadamente exponencial para SAT", Teoría y aplicaciones de las pruebas de satisfacción – SAT 2010 , Lecture Notes in Computer Science, 6175 , Springer-Verlag, págs. 313–325, doi : 10.1007 / 978- 3-642-14186-7_27 , ISBN 978-3-642-14185-0.
- Feige, Uriel ; Kilian, Joe (1997), "Sobre el no determinismo limitado versus polinomial", Chicago Journal of Theoretical Computer Science , 1 : 1–20, doi : 10.4086 / cjtcs.1997.001.
- Flum, Jörg; Grohe, Martin (2006), "16. Tratabilidad subexponencial de parámetros fijos", Teoría de la complejidad parametrizada , Textos EATCS en informática teórica, Springer-Verlag, págs. 417–451, ISBN 978-3-540-29952-3.
- Impagliazzo, Russell ; Paturi, Ramamohan (1999), "La complejidad de k-SAT", Proc. 14ª Conf. IEEE sobre complejidad computacional , págs. 237–240, doi : 10.1109 / CCC.1999.766282 , ISBN 978-0-7695-0075-1.
- Impagliazzo, Russell ; Paturi, Ramamohan; Zane, Francis (2001), "¿Qué problemas tienen una complejidad fuertemente exponencial?", Journal of Computer and System Sciences , 63 (4): 512–530, CiteSeerX 10.1.1.66.3717 , doi : 10.1006 / jcss.2001.1774.
- Karpinski, Marek ; Schudy, Warren (2010), "Algoritmos más rápidos para el torneo de conjuntos de arco de retroalimentación, torneo de agregación de rango y intermediación de Kemeny", Proc. ISAAC 2010, Parte I , Lecture Notes in Computer Science, 6506 : 3-14, arXiv : 1006.4396 , doi : 10.1007 / 978-3-642-17517-6_3 , ISBN 978-3-642-17516-9.
- Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (2011), "Los algoritmos conocidos en gráficos de ancho de árbol acotado son probablemente óptimos", Proc. 22 ° Simposio de ACM / SIAM sobre algoritmos discretos (SODA 2011) (PDF) , págs. 777–789, arXiv : 1007.5450 , Bibcode : 2010arXiv1007.5450L , archivado desde el original (PDF) el 18 de octubre de 2012 , consultado el 5 de mayo de 2011 -19.
- Pătraşcu, Mihai ; Williams, Ryan (2010), "Sobre la posibilidad de algoritmos SAT más rápidos", Proc. 21º Simposio ACM / SIAM sobre algoritmos discretos (SODA 2010) (PDF) , págs. 1065–1075.
- Williams, Ryan (2010), "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, págs. 231–240, CiteSeerX 10.1.1.216.1299 , doi : 10.1145 / 1806689.1806723 , ISBN 9781450300506.
- Woeginger, Gerhard (2003), "Algoritmos exactos para problemas NP-difíciles: una encuesta", Optimización combinatoria - Eureka, You Shrink! (PDF) , Lecture Notes in Computer Science, 2570 , Springer-Verlag, págs. 185-207, CiteSeerX 10.1.1.168.5383 , doi : 10.1007 / 3-540-36478-1_17 , ISBN 978-3-540-00580-3.