Hipótesis del tiempo exponencial

No es posible${\displaystyle s_{k}}$igualar${\displaystyle s_{\infty }}$para cualquier finito${\displaystyle k}$: como demostraron Impagliazzo, Paturi y Zane (2001) , existe una constante${\displaystyle \alpha }$de tal manera que${\displaystyle s_{k}\leq s_{\infty }(1-\alpha /k)}$Por lo tanto , si la hipótesis del tiempo exponencial es verdadera, debe haber infinitos valores de${\displaystyle k}$para qué${\displaystyle s_{k}}$difiere de${\displaystyle s_{k+1}}$. ^{[ 7 ]}

Una herramienta importante en esta área es el lema de esparsificación de Impagliazzo, Paturi y Zane (2001) , que muestra que, para cada${\displaystyle \varepsilon >0}$, cualquier${\displaystyle k}$La fórmula -CNF puede ser reemplazada por${\displaystyle O(2^{\varepsilon n})}$más simple${\displaystyle k}$Fórmulas -CNF en las que cada variable aparece solo un número constante de veces y, por lo tanto, en las que el número de cláusulas es lineal. El lema de esparcimiento 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 reemplazada por su intersección común y la otra tiene la intersección eliminada de cada cláusula. Al aplicar el lema de esparcimiento y luego usar nuevas variables para dividir las cláusulas, se puede obtener un conjunto de${\displaystyle O(2^{\varepsilon n})}$Fórmulas 3-CNF, cada una con un número lineal de variables, de tal manera que la original${\displaystyle k}$La fórmula -CNF es satisfacible si y solo si al menos una de estas fórmulas 3-CNF es satisfacible. Por lo tanto, si 3-SAT pudiera resolverse en tiempo subexponencial, se podría usar esta reducción para resolver${\displaystyle k}$-SAT también en tiempo subexponencial. Equivalentemente, si${\displaystyle s_{k}>0}$para cualquier${\displaystyle k>0}$, entonces${\displaystyle s_{3}>0}$Asimismo, la hipótesis del tiempo exponencial sería cierta. ^{[ 8 ] [ 7 ]}

El valor límite ${\displaystyle s_{\infty }}$de la secuencia de números${\displaystyle s_{k}}$es como máximo igual a${\displaystyle s_{\operatorname {CNF} }}$, dónde${\displaystyle s_{\operatorname {CNF} }}$es el ínfimo de los números${\displaystyle \delta }$de tal manera que la satisfacibilidad de fórmulas de forma normal conjuntiva sin límites de longitud de cláusula se pueda resolver en tiempo${\displaystyle O(2^{\delta n})}$Por lo tanto , si la hipótesis del tiempo exponencial fuerte es verdadera, entonces no habría ningún algoritmo para la satisfacibilidad general de CNF que sea significativamente más rápido que una búsqueda por fuerza bruta sobre todas las posibles asignaciones de verdad . Sin embargo, si la hipótesis del tiempo exponencial fuerte falla, aún sería posible${\displaystyle s_{\operatorname {CNF} }}$igualar a uno. ^{[ 9 ]}

La hipótesis del tiempo exponencial implica que muchos otros problemas de la clase de complejidad SNP no tienen algoritmos cuyo tiempo de ejecución sea más rápido que${\displaystyle c^{n}}$por alguna constante${\displaystyle c}$Estos problemas incluyen k -colorabilidad de grafos , encontrar ciclos hamiltonianos , cliques máximos , conjuntos independientes máximos y cobertura de vértices en${\displaystyle n}$-grafos 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. ^{[ 8 ] [ 7 ]}

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 encontrar camarillas o conjuntos independientes de tamaño tan pequeño es improbable que sea NP-completo, la hipótesis del tiempo exponencial implica que estos problemas no son polinomiales. ^{[ 8 ] [ 10 ]} De manera más general, la hipótesis del tiempo exponencial implica que no es posible encontrar camarillas o conjuntos independientes de tamaño${\displaystyle k}$a tiempo${\displaystyle n^{o(k)}}$. ^{[ 11 ]} La hipótesis del tiempo exponencial también implica que no es posible resolver el problema k -SUM (dado${\displaystyle n}$números reales, encontrar${\displaystyle k}$de ellos que suman cero) en el tiempo${\displaystyle n^{o(k)}}$La fuerte hipótesis del tiempo exponencial implica que no es posible encontrar${\displaystyle k}$-conjuntos dominantes de vértices más rápidamente que en tiempo${\displaystyle n^{k-o(1)}}$. ^{[ 9 ]}

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 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.${\textstyle O(2^{O({\sqrt {\operatorname {OPT} }})}n^{O(1)})}$. ^{[ 12 ]}

La hipótesis del tiempo exponencial fuerte conduce a límites ajustados en la complejidad parametrizada de varios problemas de grafos en grafos 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 grafos 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${\textstyle {\bigl (}2-o(1){\bigr )}^{w}n^{O(1)}}$y el momento óptimo para${\displaystyle k}$-colorear es${\textstyle {\bigl (}k-o(1){\bigr )}^{w}n^{O(1)}}$[ ^{13 ]} De forma equivalente, cualquier mejora en estos tiempos de ejecución refutaría la fuerte hipótesis del tiempo exponencial. ^{[ 1 ]} La hipótesis del tiempo exponencial también implica que cualquier algoritmo tratable de parámetros fijos para ^la cobertura de cliques de aristas debe tener una dependencia doblemente exponencial del parámetro. ^{[ 14 ]}

En el problema de disyunción de conjuntos de tres partes en la complejidad de la comunicación , tres subconjuntos de los enteros en algún rango${\displaystyle [1,m]}$Se especifican los conjuntos, y tres partes comunicantes conocen cada una dos de los tres subconjuntos. El objetivo es que las partes transmitan la menor cantidad de bits posible entre sí a través de un canal de comunicación compartido para que una de ellas pueda determinar si la intersección de los tres conjuntos está vacía o no. Un ejemplo trivial${\displaystyle m}$El protocolo de comunicaciones 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 si la intersección está vacía. Sin embargo, si existe un protocolo que resuelve el problema con${\displaystyle o(m)}$comunicación y${\displaystyle 2^{o(m)}}$computación, podría transformarse en un algoritmo para resolver${\displaystyle k}$-SAT a tiempo${\displaystyle O(1.74^{n})}$para cualquier constante fija${\displaystyle 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 computación. ^{[ 9 ]}

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 aún, 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 ninguna implicación para el problema P versus NP. Un argumento de relleno demuestra la existencia de problemas NP-completos para los cuales los mejores tiempos de ejecución conocidos tienen la forma${\textstyle O(2^{n^{c}})}$para${\displaystyle c<1}$y si el mejor tiempo de ejecución posible para 3-SAT fuera de esta forma, entonces P sería distinto de 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.

En la teoría de la complejidad parametrizada, debido a que la hipótesis del tiempo exponencial implica que no existe un algoritmo tratable con parámetros fijos para el clique máximo, también implica que W[1] ≠ FPT . ^{[ 11 ]} 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 parametrizada llamada jerarquía M que se intercala con la jerarquía W en el sentido de que, para todo${\displaystyle i}$,${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]\subseteq {\mathsf {M}}[i+1]}$; por ejemplo, el problema de encontrar una cobertura de vértices de tamaño${\displaystyle k\log n}$en un${\displaystyle n}$-grafo de vértices con parámetro${\displaystyle k}$es completa para M[1]. La hipótesis del tiempo exponencial es equivalente a la afirmación de que M[1] ≠ FPT , y la pregunta de si${\displaystyle {\mathsf {M}}[i]\subseteq {\mathsf {W}}[i]}$para${\displaystyle i>1}$También está abierto. ^{[ 4 ]}

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${\displaystyle A}$que resuelve la satisfacibilidad de circuitos booleanos en tiempo${\displaystyle 2^{n}/f(n)}$para alguna función de crecimiento superpolinomial${\displaystyle f}$, entonces NEXPTIME no es un subconjunto de P/poly . Williams muestra que, si el algoritmo${\displaystyle A}$existe, y también existía una familia de circuitos que simulaban NEXPTIME en P/poly, luego el algoritmo${\displaystyle A}$podría componerse con los circuitos para simular problemas NEXPTIME de forma no determinista en un tiempo menor, violando el teorema de jerarquía temporal . Por lo tanto, la existencia del algoritmo${\displaystyle A}$demuestra la inexistencia de la familia de circuitos y la separación de estas dos clases de complejidad. ^{[ 15 ]}