Existem algoritmos de tempo subexponencial para problemas de NP-completo?

51

Existem problemas completos de NP que provaram algoritmos de tempo subexponencial?

Estou solicitando informações gerais de casos, não estou falando de casos especiais tratáveis ​​aqui.

Por subexponencial, quero dizer uma ordem de crescimento acima dos polinômios, mas menor que exponencial, por exemplo .nlogn

ksb
fonte
10
O que você quer dizer com "subexponencial"? Se você quer dizer , a resposta é definitivamente sim. Se você quer dizer , acredito que a resposta é não. 2o(n)2no(1)
21813 JeffE

Respostas:

57

Depende do que você quer dizer com subexponencial. Abaixo, explico alguns significados de "subexponencial" e o que acontece em cada caso. Cada uma dessas classes está contida nas classes abaixo.


I.2no(1)

Se por subexpoencial você quer dizer , então uma conjectura na teoria da complexidade chamada ETH (Hipótese de Tempo Exponencial) implica que nenhum problema -hard pode ter um algoritmo com tempo de execução .2no(1)NP2no(1)

Observe que esta classe é fechada em composição com polinômios. Se tivermos um algoritmo de tempo subexponencial para qualquer , poderemos combiná-lo com uma redução de tempo polinomial do SAT para obter um algoritmo subexponencial para o 3SAT que violaria o ETH.NP

II , ou seja, para todos os0<ϵ2O(nϵ)2O(nϵ) 0<ϵ

A situação é semelhante à anterior.

Ele é fechado sob polinômios para que nenhum possa ser resolvido nesse período sem violar o ETH.NP


III , ou seja, para algunsϵ<12O(nϵ)2O(nϵ) ϵ<1

Se por subexponencial você quer dizer para alguns então a resposta é sim, provavelmente existem esses problemas.2O(nϵ)ϵ<1

Tome um como SAT. Possui um algoritmo de força bruta que roda no tempo . Agora considere a versão acolchoada do SAT adicionando uma sequência de tamanho às entradas:NP2O(n)nk

SAT={φ,wφSAT and |w|=|φ|k}

Agora, esse problema é -hard e pode ser resolvido no tempo .NP2O(n1k)

IV 2o(n)

Isso contém a classe anterior, a resposta é semelhante.

V. , ou seja, para todos0<ϵ2ϵn2ϵn ϵ>0

Isso contém a classe anterior, a resposta é semelhante.

VI , ou seja, para algunsϵ<12ϵn2ϵn ϵ<1

Isso contém a classe anterior, a resposta é semelhante.


O que significa subexponencial?

"Acima do polinômio" não é um limite superior, mas um limite inferior e é referido como superpolinômio .

Funções como são chamados quasipolynomial , e como o nome indica são quase polinomial e longe de ser exponencial, subexponencial é geralmente usado para se referir a classe muito maior de funções com taxas muito mais rápido crescimento.nlgn

Como o nome indica, "subexponencial" significa mais lento que exponencial . Por exponencial, geralmente queremos dizer funções na classe ou na melhor classe (que é fechada sob composição com polinômios).2Θ(n)2nΘ(1)

Subexponencial deve estar próximo desses, mas menor. Existem diferentes maneiras de fazer isso e não há um significado padrão. Podemos substituir por nas duas definições de exponencial e obter I e IV. O bom deles é que eles são definidos uniformemente (nenhum quantificador acima de ). Podemos substituir por um coeficiente multiplicativo para todos , obtemos II e V. Eles estão próximos de I e IV, mas definidos de maneira não uniforme. A última opção é substituir por uma constante multiplicativa por alguns . Isso dá II e VI.ΘoϵΘϵϵ>0Θϵϵ<1

Qual deles deve ser chamado subexponencial é discutível. Geralmente, as pessoas usam o que precisam no trabalho e se referem a ele como subexponencial.

Eu sou minha preferência pessoal, é uma classe agradável: é fechado sob composição com polinômios e é definido uniformemente. É semelhante a que usa .Exp2nO(1)

II parece ser usado na definição da classe de complexidade .SubExp

III é usado para limites superiores algorítmicos, como os mencionados na resposta de Pal.

IV também é comum.

V é usado para declarar a conjectura ETH.

As interseções ( II e V ) não são tão úteis para os limites superiores algorítmicos, seu principal uso parece ser a teoria da complexidade. Na prática, você não vai ver uma diferença entre I e II ou entre IV e V . IMHO, as três últimas definições ( IV , V , VI ) são muito sensíveis, podem ser úteis para problemas particulares, mas não são robustas, o que diminui sua utilidade como classes. Robustez e boas propriedades de fechamento fazem parte do motivo pelo qual classes de complexidade famosas, como , , ,LPNPPSpace e são interessantes.Exp

Summery

IMHO, as principais definições são I e III . Já temos algoritmos subexponenciais para no sentido de III e não podemos tê-los no sentido de I sem violar o ETH.NP

Kaveh
fonte
7
Esta resposta deve ir para a Wikipedia.
Erel Segal-Halevi
32

Apenas para listar alguns, todos com tempo de execução mais ou menos ou :2O(nlogn)nO(1)2O(n)nO(1)

Pål GD
fonte
11
Nota: esses algoritmos são um tempo subexponencial no sentido em que são executados em (para alguns ), mas não no sentido em que são executados no tempo . 2O(nϵ)ϵ<12no(1)
Kaveh