Hipótese de tempo exponencial - Exponential time hypothesis

Na teoria da complexidade computacional , a hipótese do tempo exponencial é uma suposição de dureza computacional não comprovada que foi formulada por Impagliazzo & Paturi (1999) . A hipótese afirma que o 3-SAT (ou qualquer um dos vários, mas não todos, problemas NP-completos ) não pode ser resolvido em tempo subexponencial no pior caso . A hipótese do tempo exponencial, se verdadeira, implicaria que P ≠ NP , mas é uma afirmação mais forte. 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 têm.

Definição

k -SAT é o problema de testar se uma expressão booleana , na forma normal conjuntiva com no máximo k variáveis ​​por cláusula, pode ser tornada verdadeira por alguma atribuição de valores booleanos a suas variáveis. Para cada inteiro k ≥ 2, defina um número real s k como o ínfimo dos números reais δ para os quais k -SAT pode ser resolvido algoritmicamente no tempo O (2 δ n ), onde n é o número de variáveis ​​no dado instância k -SAT. Então s 2  = 0, porque 2-SAT pode ser resolvido em tempo polinomial . Além disso, s 3  ≤  s 4  ≤ ..., uma vez que a dificuldade não diminui com o crescimento de k .

A hipótese de tempo exponencial é a conjectura de que s k  > 0 para todo k  > 2, ou, equivalentemente, que s 3  > 0.

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

Como os números s 3 , s 4 , ... formam uma sequência monotônica que é limitada acima por um, eles devem convergir para um limite s ∞ . A hipótese de tempo exponencial forte (SETH) é a conjectura de que s ∞ = 1.

Outra variante é a hipótese de tempo exponencial não uniforme , um fortalecimento do segundo fraseado da ETH, que postula que não há família de algoritmos (um para cada comprimento da entrada, no espírito do conselho ) que pode resolver 3- SAT no tempo 2 o ( n ) .

Implicações para satisfatibilidade

Não é possível que s k seja igual a s ∞ para qualquer k finito : como Impagliazzo, Paturi & Zane (2001) mostraram, existe uma constante α tal que s k  ≤  s ∞ (1 -  α / k ). Portanto, se a hipótese do tempo exponencial for verdadeira, deve haver infinitamente muitos valores de k para os quais s k difere de s k  + 1 .

Uma ferramenta importante nesta área é o lema de esparsificação de Impagliazzo, Paturi & Zane (2001) , que mostra que, para qualquer ε  > 0, qualquer fórmula k -CNF pode ser substituída por O (2 εn ) fórmulas k -CNF mais simples em em que cada variável aparece apenas um número constante de vezes e, portanto, em que o número de cláusulas é linear. O lema da esparsificação é provado encontrando repetidamente grandes conjuntos de cláusulas que têm uma interseção comum não vazia em uma determinada fórmula e substituindo a fórmula por duas fórmulas mais simples, uma das quais tem cada uma dessas cláusulas substituída por sua interseção comum e a outra tem a interseção removida de cada cláusula. Aplicando o lema de esparsificação e, em seguida, usando 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 linear de variáveis, de modo que a fórmula k -CNF original seja satisfatória se e somente se pelo menos uma dessas fórmulas 3-CNF for satisfatória. Portanto, se o 3-SAT pudesse ser resolvido em tempo subexponencial, poder-se-ia usar essa redução para resolver k- SAT também em tempo subexponencial. De forma equivalente, se s k  > 0 para qualquer k  > 3, então s 3  > 0 também, e a hipótese do tempo exponencial seria verdadeira.

O valor limite s ∞ da sequência de números s k é no máximo igual a s CNF , onde s CNF é o ínfimo dos números δ de modo que a satisfatibilidade das fórmulas normais conjuntas sem limites de comprimento de cláusula pode ser resolvida no tempo O (2 δn ). Portanto, se a hipótese de tempo exponencial forte for verdadeira, então não haveria algoritmo para satisfatibilidade geral do CNF que seja significativamente mais rápido do que testar todas as atribuições verdade possíveis . No entanto, se a hipótese do tempo exponencial forte falhar, ainda seria possível que s CNF fosse igual a um.

Implicações para outros problemas de pesquisa

A hipótese do tempo exponencial implica que muitos outros problemas na classe de complexidade SNP não têm algoritmos cujo tempo de execução é mais rápido do que c n para alguma constante  c . Estes problemas incluem gráfico k -colorability , encontrando ciclos de Hamilton , cliques máximos , conjuntos máximos independentes , e cobertura do vértice em n gráficos -vertex. Por outro lado, se qualquer um desses problemas tiver um algoritmo subexponencial, a hipótese do tempo exponencial pode ser considerada falsa.

Se cliques ou conjuntos independentes de tamanho logarítmico pudessem ser encontrados em tempo polinomial, a hipótese de tempo exponencial seria falsa. Portanto, embora encontrar cliques ou conjuntos independentes de tamanho pequeno seja improvável que seja NP-completo, a hipótese do tempo exponencial implica que esses problemas são não polinomiais. De forma mais geral, a hipótese do tempo exponencial implica que não é possível encontrar cliques ou conjuntos independentes de tamanho k no tempo n o ( k ) . A hipótese do tempo exponencial também implica que não é possível resolver o problema k -SUM (dados n números reais, encontre k deles que somam zero) no tempo n o ( k ) . A hipótese de tempo exponencial forte implica que não é possível encontrar conjuntos dominantes de k- vértices mais rapidamente do que no tempo n k  -  o (1) .

A hipótese do tempo exponencial implica também que o problema ponderado do Feedback Arc Set Tournament (FAST) não tem um algoritmo parametrizado com tempo de execução O * (2 o ( √ OPT ) ), mas possui um algoritmo parametrizado com tempo de execução O * ( 2 O ( √ OPT ) ).

A hipótese de tempo exponencial forte leva a limites estreitos na complexidade parametrizada de vários problemas de gráfico em gráficos de largura de árvore limitada . Em particular, se a hipótese de tempo exponencial forte for verdadeira, então o limite de tempo ótimo para encontrar conjuntos independentes em gráficos de largura de árvore w é (2 - o (1)) w n O (1) , o tempo ótimo para o problema de conjunto dominante é (3 - o (1)) w n O (1) , o tempo ótimo para corte máximo é (2 - o (1)) w n O (1) , e o tempo ótimo para k- coloração é ( k - o (1)) w n O (1) . De forma equivalente, qualquer melhoria nesses tempos de execução falsificaria a hipótese de tempo exponencial forte. A hipótese de tempo exponencial também implica que qualquer algoritmo tratável de parâmetro fixo para cobertura de clique de aresta deve ter dependência exponencial dupla com o parâmetro.

Implicações na complexidade da comunicação

No problema de desconexão do conjunto de três partes na complexidade da comunicação , três subconjuntos dos inteiros em algum intervalo [1, m ] são especificados, e cada uma das três partes comunicantes conhece dois dos três subconjuntos. O objetivo é que as partes transmitam poucos bits entre si em um canal de comunicação compartilhado para que uma das partes possa determinar se a interseção dos três conjuntos está vazia ou não vazia. Um protocolo de comunicações m- bit trivial seria para uma das três partes transmitir um vetor de bits que descreve a interseção dos dois conjuntos conhecidos por aquela parte, após o qual qualquer uma das duas partes restantes pode determinar o vazio da interseção. No entanto, se existe um protocolo que resolve o problema com o ( m ) e de comunicação 2 O ( m ) computação, pode ser transformado em um algoritmo para resolver k -SAT em tempo O (1,74 N ) para qualquer constante fixa k , violando a hipótese de tempo exponencial forte. Portanto, a hipótese de tempo exponencial forte implica que o protocolo trivial para a desconexão de conjuntos de três partes é ótimo ou que qualquer protocolo melhor requer uma quantidade exponencial de cálculo.

Implicações na complexidade estrutural

Se a hipótese de tempo exponencial for verdadeira, então 3-SAT não teria um algoritmo de tempo polinomial e, portanto, seguiria que P ≠ NP . Mais fortemente, neste caso, 3-SAT não poderia nem mesmo ter um algoritmo de tempo quase polinomial , então NP não poderia ser um subconjunto de QP. No entanto, se a hipótese do tempo exponencial falhar, não haverá implicação para o problema P versus NP. Existem problemas NP-completos para os quais os tempos de execução mais conhecidos têm a forma O (2 n c ) para c  <1, e se o melhor tempo de execução possível para 3-SAT fosse desta forma, então P seria diferente de NP (porque 3-SAT é NP-completo e este limite de tempo não é polinomial), mas a hipótese de tempo exponencial seria falsa.

Na teoria da complexidade parametrizada, como a hipótese do tempo exponencial implica que não existe um algoritmo tratável de parâmetros fixos para clique máximo, também implica que W [1] ≠ FPT . É um importante problema em aberto nesta área se esta implicação pode ser revertida: W [1] ≠ FPT implica a hipótese de tempo exponencial? Existe uma hierarquia de classes de complexidade parametrizada denominada hierarquia M que intercala a hierarquia W 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 k log n em um gráfico de n- vértices com parâmetro k está completo para M [1]. A hipótese do tempo exponencial é equivalente à afirmação de que M [1] ≠ FPT , e a questão de se M [ i ] = W [ i ] para i  > 1 também está em aberto.

Também é possível provar implicações na outra direção, desde o fracasso de uma variação da hipótese de tempo exponencial forte até separações de classes de complexidade. Como mostra Williams (2010) , se existe um algoritmo A que resolve a satisfatibilidade do circuito booleano no tempo 2 n / ƒ ( n ) para alguma função de crescimento superpolinomial ƒ, então NEXPTIME não é um subconjunto de P / poli . Williams mostra que, se o algoritmo A existe, e uma família de circuitos simulando NEXPTIME em P / poly também existia, então o algoritmo A poderia ser composto com os circuitos para simular problemas NEXPTIME de forma não determinística em uma quantidade menor de tempo, violando o teorema da hierarquia de tempo . Portanto, a existência do algoritmo A comprova a inexistência da família de circuitos e a separação dessas duas classes de complexidade.

Veja também

Notas

Referências

  • Calabro, Chris; Impagliazzo, Russel ; Paturi, Ramamohan (2009), "The Complexity of Satisfiability of Small Depth Circuits", Parameterized and Exact Computation, 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, setembro 10-11, 2009, Revised Selected Papers , pp. 75-85 .
  • Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A .; Xia, Ge (2006), "Fortes limites computacionais inferiores via complexidade 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), Parameterized Algorithms , Springer, p. 555, ISBN   978-3-319-21274-6
  • Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2013), "Algoritmos conhecidos para EDGE CLIQUE COVER são provavelmente ideais", Proc. 24º Simpósio ACM-SIAM sobre Algoritmos Discretos (SODA 2013) , arXiv : 1203.1754 , Bibcode : 2012arXiv1203.1754C , arquivado do original em 2013-04-16 .
  • Dantsin, Evgeny; Wolpert, Alexander (2010), "On moderately exponential time for SAT", Theory and Applications of Satisfiability Testing – SAT 2010 , Lecture Notes in Computer Science, 6175 , Springer-Verlag, pp. 313-325, doi : 10.1007 / 978- 3-642-14186-7_27 , ISBN   978-3-642-14185-0 .
  • Feige, Uriel ; Kilian, Joe (1997), "On limited versus polynomial nondeterminism", Chicago Journal of Theoretical Computer Science , 1 : 1-20, doi : 10.4086 / cjtcs.1997.001 .
  • Flum, Jörg; Grohe, Martin (2006), "16. Subexponential Fixed-Parameter Tractability", Parameterized Complexity Theory , EATCS Texts in Theoretical Computer Science, Springer-Verlag, pp. 417–451, ISBN   978-3-540-29952-3 .
  • Impagliazzo, Russell ; Paturi, Ramamohan (1999), "The Complexity of k-SAT", Proc. 14ª IEEE Conf. on Computational Complexity , pp. 237-240, doi : 10.1109 / CCC.1999.766282 , ISBN   978-0-7695-0075-1 .
  • Impagliazzo, Russell ; Paturi, Ramamohan; Zane, Francis (2001), "Quais problemas têm complexidade fortemente 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), "Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament", 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), "Algoritmos conhecidos em gráficos de largura da árvore limitada são provavelmente ótimos", Proc. 22º Simpósio ACM / SIAM sobre Algoritmos Discretos (SODA 2011) (PDF) , pp. 777-789, arXiv : 1007.5450 , Bibcode : 2010arXiv1007.5450L , arquivado do original (PDF) em 2012-10-18 , recuperado em 2011-05 -19 .
  • Pătraşcu, Mihai ; Williams, Ryan (2010), "Sobre a possibilidade de algoritmos SAT mais rápidos", Proc. 21º Simpósio ACM / SIAM sobre Algoritmos Discretos (SODA 2010) (PDF) , pp. 1065–1075 .
  • Williams, Ryan (2010), "Melhorar a pesquisa exaustiva implica limites inferiores superpolinomiais", Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010) , New York, NY, USA: ACM, pp. 231–240, CiteSeerX   10.1.1.216.1299 , doi : 10.1145 / 1806689.1806723 , ISBN   9781450300506 .
  • Woeginger, Gerhard (2003), "Algoritmos exatos para problemas NP-difíceis: Uma pesquisa", Otimização Combinatória - Eureka, You Shrink! (PDF) , Lecture Notes in Computer Science, 2570 , Springer-Verlag, pp. 185–207, CiteSeerX   10.1.1.168.5383 , doi : 10.1007 / 3-540-36478-1_17 , ISBN   978-3-540-00580-3 .