Hipótesis del tiempo exponencial

Supuesto de dureza computacional no probado

En la teoría de la complejidad computacional , la hipótesis del tiempo exponencial es un supuesto de dureza computacional no probado que fue formulado por Impagliazzo y Paturi (1999). Afirma que la satisfacibilidad de las fórmulas booleanas 3-CNF no se puede resolver en tiempo subexponencial . Más precisamente, la forma habitual de la hipótesis afirma la existencia de un número tal que todos los algoritmos que resuelven correctamente este problema requieren al menos tiempo . La hipótesis del tiempo exponencial, de ser cierta, implicaría que P ≠ NP , pero es una afirmación más contundente. Implica 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, y que muchos algoritmos conocidos para estos problemas tienen una complejidad de tiempo óptima o casi óptima . ^[1] ${\displaystyle 2^{o(n)}}$ ${\displaystyle s_{3}>0}$ ${\displaystyle 2^{s_{3}n}}$

Definición

El problema -SAT es una versión del problema booleano de satisfacibilidad en el que la entrada al problema es una expresión booleana en forma normal conjuntiva (es decir, un y de os de variables y sus negaciones) con como máximo variables por cláusula. El objetivo es determinar si se puede hacer que esta expresión sea verdadera mediante alguna asignación de valores booleanos a sus variables. 2-SAT tiene un algoritmo de tiempo lineal , pero todos los algoritmos conocidos para tamaños mayores toman tiempo exponencial , y la base de la función exponencial depende de . Por ejemplo, el algoritmo probabilístico WalkSAT puede resolver -SAT en un tiempo promedio ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

$${\displaystyle \left(2-{\frac {2}{k}}\right)^{n}n^{O(1)},}$$

instancia -SAT dada? ^[2]número entero ,-SATtiempo .mínimo-SATtiempo ., ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k\geq 3}$ ${\displaystyle s_{k}}$ ${\displaystyle k}$ ${\displaystyle 2^{s_{k}n+o(n)}}$ ${\displaystyle s_{k}}$ ${\displaystyle \delta }$ ${\displaystyle k}$ ${\displaystyle O(2^{\delta n})}$ ${\displaystyle k}$ ${\displaystyle s_{3}\leq s_{4}\leq \cdots }$

$${\displaystyle s_{k}\leq \log _{2}\left(2-{\frac {2}{k}}\right)<1.}$$

hipótesis del tiempo exponencialconjeturaesde cero. ^[1] ${\displaystyle s_{3}}$

Algunas fuentes definen la hipótesis del tiempo exponencial como la afirmación ligeramente más débil de que 3-SAT no se puede resolver a tiempo . ${\displaystyle 2^{o(n)}}$ Si existiera un algoritmo para resolver 3-SAT en el tiempo , ${\displaystyle 2^{o(n)}}$ entonces sería igual a cero. Sin embargo, es coherente con el conocimiento actual que podría haber una secuencia de algoritmos 3-SAT, cada uno con un tiempo de ejecución para una secuencia de números que tiende a cero, pero donde las descripciones de estos algoritmos están creciendo tan rápidamente que un solo algoritmo no podría seleccionará y ejecutará automáticamente el más apropiado. Si este fuera el caso, entonces sería igual a cero aunque no habría ningún algoritmo ejecutándose en el tiempo . ^[3] Una variante relacionada de la hipótesis del tiempo exponencial es la hipótesis del tiempo exponencial no uniforme , que postula que no existe una familia de algoritmos (uno para cada longitud de la entrada, en el espíritu del consejo ) que pueda resolver 3-SAT. a tiempo . ^[4] ${\displaystyle s_{3}}$ ${\displaystyle O(2^{\delta _{i}n})}$ ${\displaystyle \delta _{i}}$ ${\displaystyle s_{3}}$ ${\displaystyle 2^{o(n)}}$ ${\displaystyle 2^{o(n)}}$

Debido a que los números forman una secuencia monótona que está acotada arriba por uno, deben converger a un límite ${\displaystyle s_{3},s_{4},\dots }$

$${\displaystyle s_{\infty }=\lim _{k\to \infty }s_{k}.}$$

hipótesis del tiempo exponencial fuertede que . ^[5] ${\displaystyle s_{\infty }=1}$

Trascendencia

Satisfacción

No es posible igualar a ningún finito : como demostraron Impagliazzo, Paturi y Zane (2001), existe una constante tal que . Por lo tanto, si la hipótesis del tiempo exponencial es cierta, debe haber infinitos valores de para que difieran de . ^[6] ${\displaystyle s_{k}}$ ${\displaystyle s_{\infty }}$ ${\displaystyle k}$ ${\displaystyle \alpha }$ ${\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}$ ${\displaystyle k}$ ${\displaystyle s_{k}}$ ${\displaystyle 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 cada , ${\displaystyle \varepsilon >0}$ cualquier fórmula -CNF puede reemplazarse por fórmulas -CNF más simples en las que cada variable aparece sólo un número constante de veces. , y por tanto en el que el número de cláusulas es lineal. El lema de dispersión se demuestra 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 reemplazadas por su intersección común y la otra 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 3-CNF, cada una con un número lineal de variables, de modo que la fórmula -CNF original sea satisfactoria si y solo si al menos una de estas fórmulas de 3-CNF es satisfactoria. Por lo tanto, si 3-SAT se pudiera resolver en tiempo subexponencial, se podría usar esta reducción para resolver -SAT también en tiempo subexponencial. De manera equivalente, si fuera por alguno , entonces también, y la hipótesis del tiempo exponencial sería cierta. ^{[7] [6]} ${\displaystyle k}$ ${\displaystyle O(2^{\varepsilon n})}$ ${\displaystyle k}$ ${\displaystyle O(2^{\varepsilon n})}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle s_{k}>0}$ ${\displaystyle k>0}$ ${\displaystyle s_{3}>0}$

El valor límite de la secuencia de números es como máximo igual a , donde es el mínimo de los números tal que la satisfacibilidad de las fórmulas de forma normal conjuntiva sin límites de longitud de cláusulas se puede resolver en el tiempo . 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 una búsqueda de fuerza bruta sobre todas las asignaciones de verdad posibles . Sin embargo, si la hipótesis del tiempo exponencial fuerte falla, aún sería posible igualar a uno. ^[8] ${\displaystyle s_{\infty }}$ ${\displaystyle s_{k}}$ ${\displaystyle s_{\operatorname {CNF} }}$ ${\displaystyle s_{\operatorname {CNF} }}$ ${\displaystyle \delta }$ ${\displaystyle O(2^{\delta n})}$ ${\displaystyle s_{\operatorname {CNF} }}$

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 el de alguna constante . Estos problemas incluyen k -colorabilidad del gráfico , búsqueda de ciclos hamiltonianos , camarillas máximas , conjuntos independientes máximos y cobertura de vértices en gráficos de vértices . 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. ^{[7] [6]} ${\displaystyle c^{n}}$ ${\displaystyle c}$ ${\displaystyle n}$

Si se pudieran encontrar camarillas o conjuntos independientes de tamaño logarítmico en tiempo polinómico, 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. ^{[7] [9]} De manera más general, la hipótesis del tiempo exponencial implica que no es posible encontrar camarillas o conjuntos independientes de tamaño en el tiempo . ^[10] La hipótesis del tiempo exponencial también implica que no es posible resolver el problema k -SUM (dados los números reales, encontrar aquellos que suman cero) en el tiempo . La hipótesis del tiempo exponencial fuerte implica que no es posible encontrar conjuntos dominantes de vértices más rápidamente que en el tiempo . ^[8] ${\displaystyle k}$ ${\displaystyle n^{o(k)}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle n^{o(k)}}$ ${\displaystyle k}$ ${\displaystyle n^{k-o(1)}}$

La hipótesis del tiempo exponencial implica también que el problema del conjunto de arcos de retroalimentación ponderada en torneos no tiene un algoritmo parametrizado con el tiempo de ejecución . ${\textstyle O(2^{o({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$ Sin embargo, tiene un algoritmo parametrizado con tiempo de ejecución . ^[11] ${\textstyle O(2^{O({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$

La fuerte hipótesis del tiempo exponencial conduce a límites estrictos 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 verdadera, entonces el límite de tiempo óptimo para encontrar conjuntos independientes en gráficas de ancho de árbol ${\displaystyle w}$ es , ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$ el tiempo óptimo para el problema del conjunto dominante es , ${\textstyle {\bigl (}3-o(1){\bigr )}^{w}n^{O(1)}}$ el tiempo óptimo para el corte máximo es y ${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$ el tiempo óptimo para -colorear es . ^[12] De manera equivalente, cualquier mejora en estos tiempos de ejecución falsearía la hipótesis del tiempo exponencial fuerte. ^[13] La hipótesis del tiempo exponencial también implica que cualquier algoritmo manejable de parámetros fijos para la cobertura de camarillas de bordes debe tener una dependencia exponencial doble del parámetro. ^[14] ${\displaystyle k}$ ${\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}$

Complejidad de la comunicación

En el problema de desunión de conjuntos tripartitos en la complejidad de la comunicación , se especifican tres subconjuntos de números enteros en algún rango ${\displaystyle [1,m]}$ , y tres partes comunicantes conocen cada una dos de los tres subconjuntos. El objetivo es que las partes se transmitan la menor cantidad de 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 bits sería que una de las tres partes transmitiera un vector de bits que describiera 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 resuelva el problema de comunicación y computación, podría transformarse en un algoritmo para resolver -SAT en el tiempo para cualquier constante fija , 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 disjunción de conjuntos tripartitos es óptimo o que cualquier protocolo mejor requiere una cantidad exponencial de cálculo. ^[8] ${\displaystyle m}$ ${\displaystyle o(m)}$ ${\displaystyle 2^{o(m)}}$ ${\displaystyle k}$ ${\displaystyle O(1.74^{n})}$ ${\displaystyle k}$

Complejidad estructural

Si la hipótesis del tiempo exponencial es cierta, entonces 3-SAT no tendría un algoritmo de tiempo polinómico y, por lo tanto, se deduciría que P ≠ NP . Más claramente, en este caso, 3-SAT ni siquiera podría tener un algoritmo de tiempo cuasipolinomial , 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. Un argumento de relleno demuestra la existencia de problemas NP-completos para los cuales los tiempos de ejecución más conocidos tienen la forma para , y si el mejor tiempo de ejecución posible para 3-SAT fuera de esta forma, entonces P sería desigual a NP (porque 3- SAT es NP-completo y este límite de tiempo no es polinómico), pero la hipótesis del tiempo exponencial sería falsa. ${\textstyle O(2^{n^{c}})}$ ${\displaystyle c<1}$

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 . ^[10] Es un importante problema abierto 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 todos , ${\displaystyle i}$ ; por ejemplo, el problema de encontrar una cobertura de vértice de tamaño en un gráfico de vértice con parámetro está 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 for también está abierta. ^[3] ${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]}$ ${\displaystyle k\log n}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]}$ ${\displaystyle i>1}$

También es posible demostrar implicaciones en la otra dirección, desde el fracaso de una variación de la hipótesis del tiempo exponencial fuerte hasta separaciones de clases de complejidad. Como muestra Williams (2010), si existe un algoritmo que resuelve la satisfacibilidad del circuito booleano en el tiempo para alguna función que crece superpolinomialmente , entonces NEXPTIME no es un subconjunto de P/poly . Williams muestra que, si existe un algoritmo y también existe una familia de circuitos que simulan NEXPTIME en P/poly, entonces el algoritmo podría componerse con los circuitos para simular problemas de NEXPTIME de forma no determinista en una cantidad de tiempo menor, violando el teorema de la jerarquía del tiempo . Por tanto, la existencia del algoritmo prueba la inexistencia de la familia de circuitos y la separación de estas dos clases de complejidad. ^[15] ${\displaystyle A}$ ${\displaystyle 2^{n}/f(n)}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

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

1. Impagliazzo, Russell ; Paturi, Ramamohan (1999), "La complejidad de k-SAT", Proc. 14ª Conferencia IEEE. sobre complejidad computacional , págs. 237–240, doi :10.1109/CCC.1999.766282, ISBN 978-0-7695-0075-1, S2CID  442454
2. Schöning, Uwe (1999), "Un algoritmo probabilístico para -SAT y problemas de satisfacción de restricciones", 40º Simposio anual sobre fundamentos de la informática, FOCS '99, 17-18 de octubre de 1999, Nueva York, NY, EE. UU. , IEEE Computer Sociedad, págs. 410–414, doi :10.1109/SFFCS.1999.814612, S2CID  1230959 ${\displaystyle k}$
3. Flum, Jörg; Grohe, Martin (2006), "16. Tractabilidad subexponencial de parámetros fijos", Teoría de la complejidad parametrizada , Textos EATCS en informática teórica, Springer-Verlag, págs . 978-3-540-29952-3
4. Chen, Yijia; Eickmeyer, Kord; Flum, Jörg (2012), "La hipótesis del tiempo exponencial y el problema de la camarilla parametrizada", en Thilikos, Dimitrios M.; Woeginger, Gerhard J. (eds.), Computación exacta y parametrizada - Séptimo simposio internacional, IPEC 2012, Ljubljana, Eslovenia, 12 al 14 de septiembre de 2012, Actas , Lecture Notes in Computer Science, vol. 7535, Springer, págs. 13–24, CiteSeerX 10.1.1.680.8401 , doi :10.1007/978-3-642-33293-7_4 
5. Calabro, Chris; Impagliazzo, Russell ; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits", Computación exacta y parametrizada, 4º taller internacional, IWPEC 2009, Copenhague, Dinamarca, 10 y 11 de septiembre de 2009, artículos seleccionados revisados , notas de conferencias sobre informática , vol. 5917, págs. 75–85, CiteSeerX 10.1.1.331.764 , doi :10.1007/978-3-642-11269-0_6 
6. 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 
7. Woeginger, Gerhard (2003), "Algoritmos exactos para problemas NP-difíciles: una encuesta", Optimización combinatoria - ¡Eureka, te encoges! (PDF) , Apuntes de conferencias sobre informática, vol. 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, S2CID  289357, archivado desde el original (PDF) el 30 de septiembre de 2020 , consultado el 31 de marzo de 2011
8. Pătraşcu, Mihai ; Williams, Ryan (2010), "Sobre la posibilidad de algoritmos SAT más rápidos", Proc. XXI Simposio ACM/SIAM sobre algoritmos discretos (SODA 2010) (PDF) , págs.
9. 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
10. Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge (2006), "Fuertes límites computacionales inferiores mediante complejidad parametrizada", Journal of Computer and System Sciences , 72 (8): 1346–1367, doi : 10.1016/j.jcss.2006.04.007
11. Karpinski, Marek ; Schudy, Warren (2010), "Algoritmos más rápidos para el torneo de conjunto de arcos de retroalimentación, torneo de intermediación y agregación de rangos de Kemeny", Proc. ISAAC 2010, Parte I , Apuntes de conferencias sobre informática, 6506 : 3–14, arXiv : 1006.4396 , doi :10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9, S2CID  16512997
12. Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015), Algoritmos parametrizados , Springer, pág. 555, ISBN 978-3-319-21274-6
13. Lokshtanov, Daniel; Marx, Daniel; Saurabh, Saket (2011), "Los algoritmos conocidos en gráficos de ancho de árbol acotado probablemente sean óptimos", Proc. 22.º Simposio ACM/SIAM sobre algoritmos discretos (SODA 2011) , págs. 777–789, arXiv : 1007.5450 , doi : 10.1137/1.9781611973082.61, S2CID  1810488
14. Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Los algoritmos conocidos para la cobertura de camarillas de bordes probablemente sean óptimos", SIAM Journal on Computing , 45 (1): 67–83, arXiv : 1203.1754 , doi :10.1137/130947076, MR  3448348, S2CID  11264145
15. 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, S2CID  651703

Otras lecturas

• Dantsin, Evgeny; Wolpert, Alexander (2010), "En un tiempo moderadamente exponencial para el SAT", Teoría y aplicaciones de las pruebas de satisfacción – SAT 2010 , Lecture Notes in Computer Science, vol. 6175, Springer-Verlag, págs. 313–325, doi :10.1007/978-3-642-14186-7_27, ISBN 978-3-642-14185-0