Hipótese do tempo exponencial

Na teoria da complexidade computacional, a hipótese de tempo exponencial é uma suposição computacional de dureza não comprovada, formalizada por Impagliazzo e Paturi (1999), afirmando que o 3-SAT (ou qualquer um dos vários relacionados com problemas NP-completos) não pode ser resolvido em tempo subexponencial no pior caso. A hipótese de tempo exponencial, se verdadeira, implicaria que P ≠ NP. Ele pode ser usado para mostrar que muitos problemas computacionais são equivalentes em complexidade, no sentido de que, se um deles tem um algoritmo de tempo subexponencial, então todos eles fazem.

Definição

O k-SAT é o problema de testar se uma fórmula booleana, na forma normal conjuntiva com a maioria das variáveis ​​de K por cláusula, pode ser feita para ser verdade por alguma atribuição de valores booleana às suas variáveis. Para cada inteiro k ≥ 2, define-se um número real sk a ser o ínfimo dos números reais ô, para os quais existe um algoritmo de solução de k-SAT em tempo O (2δn), onde n é o número de variáveis ​​no exemplo k- SAT dado. Então, s2 = 0, pois 2-SAT pode ser resolvido em tempo polinomial. A hipótese de tempo exponencial é a conjectura de que, para cada k > 2, sk > 0. Claramente, s3 ≤ s4 ≤ ..., por isso é equivalente a assumir que s3 > 0; a positividade dos restantes números sk segue automaticamente a partir deste pressuposto.

Algumas fontes definem a hipótese de tempo exponencial para ser a instrução ligeiramente mais fraca de que o 3-SAT não pode ser resolvido em tempo 2o (n). Se existisse um algoritmo para resolver 3-SAT em tempo 2o (n), em seguida, claramente s3 seria igual a zero. No entanto, é consistente com o conhecimento atual que poderia haver uma sequência de algoritmos 3-SAT, cada um com funcionamento em tempo O (2δin) para uma sequência de números δi tendendo a zero, mas onde as descrições desses algoritmos são tão rapidamente crescentes que um único algoritmo não poderia automaticamente selecionar e executar o mais adequado.

Como os números s3, s4, ... formam uma sequência monótona que é delimitada por uma acima, eles devem convergir a um limite s∞. A hipótese de tempo forte exponencial é a suposição de que o valor limite s∞ da sequência de números sk é igual a um.

Implicações

Satisfatibilidade

Não é possível para sk ser igual a s∞ para qualquer k finito: como Impagliazzo, Paturi e Zane (2001) demonstraram, existe uma α constante, de tal modo que sk ≤ s ∞ (1 - α / k). Portanto, se a hipótese de tempo exponencial é verdade, tem de haver um número infinito de valores de k, ao qual difere de sk + 1.

Uma ferramenta importante nesta área é o lema sparsification de Impagliazzo, Paturi e Zane (2001), que mostra que, para qualquer ε > 0, qualquer fórmula k-CNF pode ser substituída por fórmulas O (2εn) k-CNF mais simples, em que cada variável aparece apenas um número constante de vezes, e, por conseguinte, em que o número de cláusulas é linear. O lema sparsification é comprovado por várias vezes encontrar grandes conjuntos de cláusulas que têm uma intersecção não vazia comum em uma fórmula dada; e substituindo a fórmula por duas fórmulas mais simples, em que uma das quais tem cada uma destas cláusulas substituída por sua intersecção comum; e a outra das quais tem a intersecção removida de cada cláusula. Ao aplicar o lema sparsification e, em seguida, utilizando novas variáveis ​​para dividir as cláusulas, pode-se então obter um conjunto de fórmulas O (2εn) 3-CNF, cada uma com um número de variáveis ​​linear, de tal modo que a fórmula k-CNF original é satisfatível se, e apenas se, pelo menos, uma destas fórmulas 3-CNF for satisfatória. Portanto, se 3-SAT poderia ser resolvido em tempo subexponencial, um poderia usar esta redução para resolver k-SAT em tempo subexponencial tão bem. Equivalentemente, se sk > 0 para qualquer k > 3, então s3 > 0; e a hipótese de tempo exponencial seria verdade.

O valor limitante s^∞ da sequência de números sk é no máximo igual a SCNF, onde SCNF é o ínfimo dos números ô satisfatíveis, tal que a forma normal de fórmulas conjuntivas de cláusula l sem limites de comprimento pode ser resolvida em tempo O (2δn). Portanto, se a hipótese de tempo exponencial forte é verdade, então não haveria nenhum algoritmo geral para satisfazer CNF, que é significativamente mais rápido do que testar todas as atribuições de verdade possíveis. No entanto, se a hipótese de tempo forte exponencial falhar, seria ainda possível para SCNF para igualar uma.

Outros problemas de busca

A hipótese de tempo exponencial implica que os problemas de muitos outros na classe de complexidade SNP não têm algoritmos cujo tempo de corrida é mais rápido que cn para algum c constante. Esses problemas incluem um gráfico k-coloração, encontrando ciclos hamiltonianos, máximo de panelinhas, máximo de conjuntos independentes e cobertura de vértice de n-vértices gráficos. Por outro lado, se qualquer um desses problemas tem um algoritmo subexponencial, então a hipótese de tempo exponencial poderia ser mostrada para ser falsa.

Se cliques ou conjuntos independentes de tamanho logarítmico pode ser encontrado em tempo polinomial, a hipótese de tempo exponencial seria falsa. Portanto, embora sejam encontradas panelinhas ou conjuntos independentes de pequeno tamanho tal, é improvável que seja NP-completa, a hipótese de tempo exponencial implica que estes problemas são não polinomiais. Mas geralmente, a hipótese de tempo exponencial implica que não é possível encontrar panelinhas ou conjuntos independentes de tamanho k em tempo não (k). A hipótese de tempo exponencial também implica que não é possível resolver o problema k SUM-(dado n números reais, encontrar k deles que adicionem a zero) em tempo não (k). A hipótese de tempo forte exponencial implica que não é possível encontrar k-vértice dominando conjuntos mais rapidamente do que no tempo nk -. O (1).

A hipótese de tempo forte exponencial leva a limites rigorosos da complexidade parametrizada de problemas gráficos sobre diversos gráficos de treewidth limitada. Em particular, se a hipótese de tempo exponencial forte é verdadeira, então o tempo óptimo para encontrar conjuntos ligados independentes em grafos de treewidth w é (2 - o (1)) wnO (1); e o tempo óptimo para o problema conjunto dominante é ( 3 - o (1)) wnO (1), o tempo óptimo para máximo de corte é (2 - o (1)) wnO (1); e o tempo óptimo à k-coloração é (k - o (1)) wnO (1). Equivalentemente, qualquer melhoria nestes tempos de execução seria falsificar a hipótese de tempo forte exponencial.

Complexidade da comunicação

No problema de disjunção de três partes em um conjunto de complexidade de comunicação, três subconjuntos dos inteiros em algum intervalo [1, m] são especificados; e três partes que se comunicam conhecem dois dos três subgrupos cada. O objetivo é que as partes possam transmitir como poucos bits sobre um canal de comunicações ao outro comum, a fim de que uma das partes seja capaz de determinar se a intersecção dos três conjuntos é vazia ou não vazia. Um protocolo de comunicações trivial de m bits iria, a um dos três partidos, transmitir um BitVector que descreve a interseção dos dois conjuntos que se sabe o partido, após o que nenhuma das duas partes restantes podem determinar como o vazio do cruzamento. No entanto, se existe um protocolo que resolve o problema com o (m) comunicação e 2o computação (m), então poderia ser transformado em um algoritmo para resolver o k-SAT, em tempo O (1.74n), para qualquer constante fixa k, violando a hipótese de tempo forte exponencial. Portanto, a hipótese de tempo forte exponencial implica tanto que o protocolo do conjunto trivial de três partes-disjunção é o ideal; ou melhor, que qualquer protocolo requer uma quantidade exponencial da computação.

Complexidade estrutural

Se a hipótese de tempo exponencial é verdade, então 3-SAT não teria um algoritmo de tempo polinomial; e, portanto, segue-se que P ≠ NP. Mais fortemente, neste caso, 3-SAT não poderia mesmo ter um algoritmo de tempo quase-polinomial, de modo que NP não poderia ser um subconjunto de QP. No entanto, se a hipótese de tempo exponencial falhar, ele não teria nenhuma implicação para o problema P versus NP. Existem problemas NP-completos aos quais os mais conhecidos tempos de execução têm a forma O (2NF) para c < 1; e se o melhor tempo possível correndo para 3-SAT for desta forma, então P seria desigual a NP (porque 3-SAT é NP-completo; e desta vez não é obrigado a ser polinomial), mas a hipótese de tempo exponencial seria falsa.

Em teoria da complexidade parametrizada, porque a hipótese de tempo exponencial implica que não existe um algoritmo pré-parâmetro-tratável por clique máximo, ele também implica que W [1] ≠ FPT. É um importante problema em aberto nesta área se essa implicação pode ser revertida: fazer W [1] ≠ FPT implica a hipótese de tempo exponencial? Há uma hierarquia de classes de complexidade parametrizadas, chamada de M-hierarquia, que intercala a W-hierarquia no sentido de que, para todo i, M [i] ⊆ W [i] ⊆ M [i + 1], por exemplo, o problema de encontrar uma cobertura de vértices de tamanho log k n em um gráfico de n-vértice com o parâmetro k é completo para M [1]. A hipótese de tempo exponencial é equivalente à afirmação de que M [1] ≠ FPT; e a questão de saber se M [i] = W [i] para i > 1 também está aberta.

Também é possível provar implicações na outra direção, a partir da falha de uma variação da hipótese de tempo forte exponencial para separações de classes de complexidade. Como Williams (2010) mostra, no caso de existir um algoritmo A que resolve a satisfatibilidade de um circuito booleano em tempo 2n / ƒ (n), para alguma função ƒ superpolinomial crescente, em seguida, NEXPTIME não é um subconjunto de P/polinomial. Williams mostra que, se o algoritmo A existir, e uma família de circuitos que simulam NEXPTIME em P/poli exista também, em seguida, o algoritmo A pode ser composto com os circuitos para simular problemas NEXPTIME não deterministicamente em uma quantidade menor de tempo, violando o teorema de hierarquia de tempo. Portanto, a existência de um algoritmo A prova a inexistência da família de circuitos e da separação das duas classes de complexidade.