Hipótese do tempo exponencial

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de en:Exponential time hypothesis (desde janeiro de 2013). Ajude e colabore com a tradução.
Wikitext.svg
Este artigo ou seção precisa ser wikificado (desde janeiro de 2013).
Por favor ajude a formatar este artigo de acordo com as diretrizes estabelecidas no livro de estilo.
Question book.svg
Esta página ou secção não cita nenhuma fonte ou referência, o que compromete sua credibilidade (desde julho de 2012).
Por favor, melhore este artigo providenciando fontes fiáveis e independentes, inserindo-as no corpo do texto por meio de notas de rodapé. Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

Na teoria da complexidade computacional, a hipótese de tempo exponencial é uma suposição dureza não comprovada computacional 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 subexponential 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 subexponential então todos eles fazem.

Definição[editar | editar código-fonte]

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 alguns atribuição de valores booleana à sua variáveis. Para cada inteiro k ≥ 2, definem uma sk número real a ser o ínfimo dos números reais ô para o qual existe um algoritmo de solução de k-SAT em tempo O (2δn), onde n é o número de variáveis ​​no dada k- SAT exemplo. 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 definir a hipótese de tempo exponencial para ser a instrução ligeiramente mais fraco 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 seqüência de 3-SAT algoritmos, cada um com funcionamento em tempo O (2δin) para uma seqüência de números δi tendendo a zero, mas onde as descrições desses algoritmos são tão rapidamente crescente de que um único algoritmo não poderia automaticamente selecionar e executar o mais adequado.

Como os números S3, S4, ... formar uma sequência monótona que é delimitada por uma acima, eles devem convergem para um limite s ∞. A hipótese de tempo forte exponencial é a suposição de que o valor limite s ∞ da seqüência de números sk igual a um

Implicações para satisfatibilidade[editar | editar código-fonte]

Não é possível para a SK igual 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 para o qual difere de sk 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ído por O (2εn) mais simples k-CNF fórmulas 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 é comprovada 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, um dos quais tem cada uma destas cláusulas substituído por sua intersecção comum ea 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 O (2εn) 3-CNF fórmulas, cada um 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 é satisfatório. Portanto, se 3-SAT poderia ser resolvido em tempo subexponential, um poderia usar esta redução para resolver k-SAT em tempo subexponential tão bem. Equivalentemente, se sk> 0 para qualquer k> 3, então s3> 0, bem como, ea hipótese de tempo exponencial seria verdade.

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

Implicações para outros problemas de busca[editar | editar código-fonte]

A hipótese de tempo exponencial implica que os problemas de muitos outros na complexidade classe SNP não têm algoritmos cujo tempo de corrida é mais rápido que cn para algum c constante. Esses problemas incluem gráfico k-coloração, encontrando ciclos hamiltonianos, panelinhas máximo, 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 subexponential, então a hipótese de tempo exponencial poderia ser mostrado para ser falsa.

Se cliques ou conjuntos independentes de tamanho logarítmica pode ser encontrado em tempo polinomial, a hipótese de tempo exponencial seria falsa. Portanto, embora encontrando 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-polinomial. Mais geralmente, a hipótese de tempo exponencial implica que ele não é possível encontrar panelinhas ou conjuntos independentes de tamanho k em tempo não (k). [7] A hipótese tempo exponencial também implica que não é possível resolver o problema k SUM-(dado n números reais, encontrar k deles que adicionar 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 ligado conjuntos independentes em grafos de treewidth w é (2 - o (1)) wnO (1), 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), eo tempo óptimo para a 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. [8]

Implicações da complexidade da comunicação[editar | editar código-fonte]

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

Implicações na complexidade estrutural[editar | editar código-fonte]

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 quasi-polinomial, de modo 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 para os 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 foram desta forma, então P seria desigual a NP (porque 3-SAT é NP-completo e desta vez não é obrigado polinomial), mas a hipótese de tempo exponencial seria falsa.

Em parametrizado teoria da complexidade, 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. [7] É um importante problema em aberto nesta área se essa implicação pode ser revertido: faz W [1] ≠ FPT implica a hipótese de tempo exponencial? Há uma hierarquia de classes de complexidade parametrizados chamado de M-hierarquia que intercala o 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 é completa para M [1]. A hipótese de tempo exponencial é equivalente à afirmação de que M [1] ≠ FPT, ea questão de saber se M [i] = W [i] para i > 1 também está aberto.

Também é possível provar implicações na outra direcçã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 satisfatibilidade circuito booleano em tempo 2n / ƒ (n) para alguma função ƒ superpolynomially crescente, em seguida, NEXPTIME não é um subconjunto de P / poli. Williams mostra que, se o algoritmo A existir, e uma família de circuitos que simulam NEXPTIME em P / poli existia também, em seguida, algoritmo A pode ser composta com os circuitos para simular problemas NEXPTIME nondeterministically em uma quantidade menor de tempo, violar o teorema de hierarquia de tempo. Portanto, a existência de algoritmo A prova a inexistência da família de circuitos e da separação das duas classes de complexidade.