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

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 .$n^{\log n}$

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.$2^{n^{o(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 .$2^{n^{o(1)}}$$\mathsf{NP}$$2^{n^{o(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.$\mathsf{NP}$

II , ou seja, para todos os$\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$$2^{O(n^\epsilon)}$ $0 < \epsilon$

A situação é semelhante à anterior.

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

III , ou seja, para alguns$\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$$2^{O(n^\epsilon)}$ $\epsilon < 1$

Se por subexponencial você quer dizer para alguns então a resposta é sim, provavelmente existem esses problemas.$2^{O(n^\epsilon)}$$\epsilon<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:$\mathsf{NP}$$2^{O(n)}$$n^k$

Agora, esse problema é -hard e pode ser resolvido no tempo .$\mathsf{NP}$$2^{O(n^\frac{1}{k})}$

IV $2^{o(n)}$

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

V. , ou seja, para todos$\bigcap_{0 < \epsilon}2^{\epsilon n}$$2^{\epsilon n}$ $\epsilon>0$

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

VI , ou seja, para alguns$\bigcup_{\epsilon < 1}2^{\epsilon n}$$2^{\epsilon n}$ $\epsilon<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.$n^{\lg n}$

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^{\Theta(n)}$$2^{n^{\Theta(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.$\Theta$$o$$\epsilon$$\Theta$$\epsilon$$\epsilon>0$$\Theta$$\epsilon$$\epsilon<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 .$\mathsf{Exp}$$2^{n^{O(1)}}$

II parece ser usado na definição da classe de complexidade .$\mathsf{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 , , ,$\mathsf{L}$$\mathsf{P}$$\mathsf{NP}$$\mathsf{PSpace}$ e são interessantes.$\mathsf{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.$\mathsf{NP}$

Apenas para listar alguns, todos com tempo de execução mais ou menos ou :$2^{O(\sqrt{n} \log n)}n^{O(1)}$$2^{O(\sqrt{n})}n^{O(1)}$

• Arco de feedback definido nos torneios [Noga Alon, Daniel Lokshtanov, Saket Saurabh, ALP 2009]
• Preenchimento mínimo e conclusão da cadeia [Fomin and Villanger SODA 2012]
• Exclusão de borda dividida [Ghosh et al SWAT 2012]
• Edição de cluster com clusters$t$ [Fomin et al STACS 2013]
• Muitos problemas de bidimensionalidade, diferentes problemas gráficos em gráficos de gênero limitado e especialmente gráficos planares (consulte Demaine, Fomin, Hajiaghayi, Thilikos: algoritmos parametrizados subexponenciais em gráficos de gênero limitado e gráficos sem H menor )
• Algoritmo parametrizado no tempo subexponencial para árvore Steiner em gráficos planares [Pilipczuk et al STACS 2013]
• Conclusão trivialmente perfeita, conclusão de limite e conclusão com pseudos-divisões [D. et al STACS 2014]
• Conclusão de intervalo [Bliznets et al]
• Conclusão apropriada do intervalo [Bliznets et al]