Problèmes de décision en

Quels sont quelques exemples de problèmes de décision difficiles qui peuvent être résolus en temps polynomial? Je recherche des problèmes pour lesquels l'algorithme optimal est "lent", ou des problèmes pour lesquels l'algorithme connu le plus rapide est "lent".

Voici deux exemples:

• Reconnaissance de graphes parfaits. Dans leur article FOCS'03 [1] Cornuéjols, Liu et Vuskovic ont donné un algorithme de temps pour le problème, où est le nombre de sommets. Je ne sais pas si cette limite a été améliorée, mais si je comprends bien, plus ou moins une percée est nécessaire pour obtenir un algorithme plus rapide. (Les auteurs donnent un algorithme de temps dans la version journal de [1], voir ici ).$O(n^{10})$$n$$O(n^9)$

• Reconnaissance des graphiques cartographiques. Thorup [2] a donné un algorithme assez complexe avec l'exposant étant (environ?) . Peut-être que cela a même été considérablement amélioré, mais je n'ai pas de bonne référence.$120$

Je m'intéresse particulièrement aux problèmes qui ont une importance pratique, et l'obtention d'un algorithme "rapide" (ou même pratique) est ouverte depuis plusieurs années.

[1] Cornuéjols, Gérard, Xinming Liu et Kristina Vuskovic. "Un algorithme polynomial pour reconnaître des graphes parfaits." Foundations of Computer Science, 2003. Actes. 44e Symposium annuel de l'IEEE sur. IEEE, 2003.

[2] Thorup, Mikkel. "Graphiques cartographiques en temps polynomial." Foundations of Computer Science, 1998. Actes. 39e Symposium annuel sur. IEEE, 1998.

Peut-être que les problèmes suivants correspondent à vos exemples:

• (La version de décision de) Coloration, Clique, Ensemble stable, Couverture de clique dans des graphiques parfaits. Jusqu'à présent, les seuls algorithmes polynomiaux temporels connus pour ces problèmes sont basés sur la méthode ellipsoïde, qui est «lente» (et numériquement instable).

• Test de primalité AKS en temps . Malgré de nombreuses améliorations (actuellement O ( ( log n ) 7.5 ) ), l'algorithme AKS est encore trop lent dans la pratique.$O((\log n)^{12})$$O((\log n)^{7.5})$

Il y a une question similaire sur cstheory , avec de nombreux exemples allant des algorithmes "réalistes et impraticablement lents" avec des exposants de 6 ou 7 vers le haut. Cette question traite également des grandes constantes.

Il y a un classique que je veux reproduire car il semble être un exemple si horriblement spectaculaire du temps polynomial (volé sans vergogne à la réponse 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, An Energy-Driven Approach to Linkage Unfolding , SOCG 2004.