Algorithmes puissants trop complexes à implémenter

Quels sont les algorithmes d’utilité légitime tout simplement trop complexes à mettre en œuvre?

Soyons clairs: je ne cherche pas d’algorithmes comme l’algorithme actuel de multiplication de matrice optimale asymptotique (Coppersmith-Winograd), qu’il est raisonnable de mettre en œuvre mais dont la constante est inutile en pratique. Je recherche des algorithmes susceptibles d'avoir une valeur pratique, mais ils sont si difficiles à coder qu'ils n'ont jamais été implémentés, mis en œuvre uniquement dans des environnements extrêmement artificiels, ou mis en œuvre uniquement pour des applications remarquablement spéciales.

Des algorithmes presque impossibles à mettre en œuvre sont également les bienvenus. Ils présentent de bonnes asymptotiques, mais leurs performances réelles sont probablement médiocres.

Chazelle a donné un algorithme de temps linéaire pour trianguler un polygone simple . Skiena a écrit (p. 575, Manuel de conception d'algorithmes) qu'il était "suffisamment désespéré pour être mis en oeuvre de sorte qu'il soit davantage qualifié de preuve d'existence"

L' algorithme de Risch pour le calcul des primitives élémentaires. Selon Wikipedia, aucun logiciel n'est connu pour implémenter l'algorithme complet en raison de sa complexité.

Tout algorithme qui utilise les résultats de Robertson-Seymour pour déduire un algorithme "polytime" pour des choses impliquant des graphes qui excluent un mineur fixe pose des problèmes. La constante cachée dans leur résultat est "galactique".

$O(n)$$O(\frac{\log^2 n}{B})$$B$

Le document fait 55 pages et sa conclusion note plusieurs améliorations aux constantes que l'auteur ne décrit pas pour des raisons d'espace. Cela me fait penser que les constantes ne sont peut-être pas si galactiques et que cette structure de données serait "d'utilité légitime", d'autant plus qu'elle a été citée à plusieurs reprises.

L'algorithme d'unification de modèle d'ordre supérieur à temps linéaire de Qian n'a jamais été mis en œuvre en raison de sa complexité telle que je l'avais mentionné.

Algorithme linéaire pour vérifier si un graphique peut être intégré dans une surface fixe.

Ken-ichi Kawarabayashi, Bojan Mohar, Bruce A. Reed: Un algorithme linéaire plus simple pour l’incorporation de graphes dans une surface arbitraire et le genre des graphes de largeur d’arbre délimité. FOCS 2008: 771-780.

Bojan Mohar: Algorithme temporel linéaire pour l'incorporation de graphes dans une surface arbitraire. SIAM J. Discrete Math. 12 (1): 6-26 (1999)

Je ne sais pas si cela pourrait être utile en pratique (même si je pense au repliement et à la comparaison de protéines, ainsi qu’à la prédiction de la structure secondaire de l’ARN), mais Wolfgang Haken a donné le premier algorithme en temps polynomial permettant de décider si un noeud est un noeud. boucle simple ( Theorie der Normalflächen. Acta Math. 105, 1961, pp. 245–375). Si je me souviens bien, c'est encore trop compliqué à mettre en œuvre toutes ces décennies plus tard.

Si l'on en croit Wikipedia, plusieurs autres algorithmes ont été donnés plus tard, et "Comprendre la complexité de ces algorithmes est un domaine d'étude actif.".

Décomposition des arbres , et peut-être des tas de Fibonacci .

Une construction de hachage parfaite ( https://en.wikipedia.org/wiki/Perfect_hash_function#Construction ) s'appliquerait à tous les cas d'utilisation avec des clés statiques ou peu changeantes (par exemple, noms de domaine de niveau supérieur sur les routeurs, mots-clés dans les compilateurs ou noms de fonction dans les bibliothèques standard), mais la dernière fois que j’ai regardé, je n’ai trouvé aucune implémentation.

La recherche paramétrique peut résoudre de nombreux problèmes d'optimisation difficiles, y compris ceux qui pourraient sembler devoir être NP-difficiles, en temps polynomial. La recherche papier bien nommée Parametric made pratique implémente une variante de la recherche paramétrique, mais je ne pense toujours pas qu'elle ait été implémentée dans un logiciel pratique.

$k$$n$$O(n \log n + k)$$O((n+k) \log n)$