Problemas de decisão em

Quais são alguns exemplos de problemas difíceis de decisão que podem ser resolvidos em tempo polinomial? Estou procurando problemas para os quais o algoritmo ideal é "lento" ou problemas para os quais o algoritmo mais rápido conhecido é "lento".

Aqui estão dois exemplos:

• Reconhecimento de gráficos perfeitos. Em seu trabalho no FOCS'03 [1] Cornuéjols, Liu e Vuskovic forneceram um algoritmo de tempo $O(n^{10})$ para o problema, onde $n$ é o número de vértices. Não tenho certeza se esse limite foi aprimorado, mas, pelo que entendi, é necessário mais ou menos um avanço para obter um algoritmo mais rápido. (Os autores fornecem um algoritmo de tempo $O(n^9)$ na versão do diário de [1], veja aqui ).

• Reconhecimento de gráficos de mapas. Thorup [2] deu um algoritmo bastante complexo com o expoente sendo (cerca de?) $120$ . Talvez isso tenha sido dramaticamente aprimorado, mas não tenho uma boa referência.

Estou especialmente interessado em problemas que têm importância prática e a obtenção de um algoritmo "rápido" (ou mesmo prático) está aberta há vários anos.

[1] Cornuéjols, Gérard, Xinming Liu e Kristina Vuskovic. "Um algoritmo polinomial para reconhecer gráficos perfeitos." Fundações de Ciência da Computação, 2003. Proceedings. 44º Simpósio Anual do IEEE em. IEEE, 2003.

[2] Thorup, Mikkel. "Mapear gráficos em tempo polinomial." Fundações de Ciência da Computação, 1998. Proceedings. 39º Simpósio Anual em. IEEE, 1998.

Talvez os seguintes problemas se encaixem nos seus exemplos:

• (A versão de decisão de) Coloração, Clique, Conjunto Estável, Cobertura de Clique em gráficos perfeitos. Até agora, os únicos algoritmos de tempo polinomial conhecidos para esses problemas são baseados no método elipsóide, que é '' lento '' (e numericamente instável).

• Teste de primalidade AKS no tempo . Apesar de muitas melhorias (atualmente O ( ( log n ) 7.5 ) ), o algoritmo AKS ainda é muito lento na prática.$O((\log n)^{12})$$O((\log n)^{7.5})$

Há uma pergunta semelhante sobre a história , com muitos exemplos que variam dos algoritmos "realisticamente impraticamente lentos" com expoentes de 6 ou 7 para cima. Essa pergunta também discute grandes constantes também.

Há um clássico que quero reproduzir, pois parece um exemplo espetacularmente horrível de tempo polinomial (descaradamente roubado da resposta de JeffE):

$1752484608000n^{79}L^{25}/D^{26}(\Theta_0)$

$117607251220365312000n^{79}(\ell_{max}/d_{min}(\Theta_0))^{26}.$

De: Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, James F. O'Brien, Uma abordagem orientada a energia para o desdobramento de ligações, SOCG 2004.