Des problèmes qui peuvent être résolus de manière contre-intuitive dans la pratique?

Récemment, j'ai vécu l' expérience douloureuse et amusante d'expliquer de manière informelle le concept de complexité informatique à un jeune programmeur autodidacte talentueux, qui n'avait jamais suivi de cours formel en algorithmes ou en complexité auparavant. Sans surprise, beaucoup de notions semblaient étranges au début mais avaient du sens avec certains exemples (PTIME, intractabilité, non calculabilité) , tandis que d'autres semblent venir plus naturellement (classification des problèmes via les réductions, temps et espace comme ressources, analyse asymptotique) . Tout allait bien jusqu'à ce que j'admette accidentellement que SATpeut être résolu efficacement * dans la pratique ... Et juste comme ça, je les ai perdus. Peu importait la façon convaincante dont j'essayais de plaider pour la théorie, le gamin était convaincu que ce n'était que des conneries artificielles dont il ne devrait pas se soucier. Bien...

¯ \ _ (ツ) _ / ¯

Non, je n'avais pas le cœur brisé, et je ne me souciais pas vraiment de ce qu'il pensait, ce n'est pas le but de cette question. Notre conversation m'a fait penser à une question différente,

Que sais-je vraiment des problèmes qui sont théoriquement insolubles (complexité temporelle superpolynomiale) mais pratiquement résolubles (via des heuristiques, des approximations, des solveurs SAT, etc.)?

J'ai réalisé, pas grand-chose. Je sais qu'il existe des solveurs SAT très efficaces qui résolvent efficacement d'énormes instances, que Simplex fonctionne très bien dans la pratique et peut-être quelques problèmes ou algorithmes supplémentaires. Pouvez-vous m'aider à brosser un tableau plus complet? Quels sont les problèmes connus ou même les classes de problèmes dans cette catégorie?

TL; DR: Quels sont les problèmes qui peuvent être résolus de manière contre-intuitive dans la pratique? Existe-t-il une ressource (mise à jour) pour en savoir plus? Avons-nous une caractérisation pour eux? Et, enfin, en tant que question de discussion générale, ne devrions-nous pas?

EDIT # 1: En essayant de répondre à ma dernière question de discussion sur une telle caractérisation , j'ai été initié à l' analyse lissée des algorithmes, un concept introduit par Daniel Spielman et Shang-Hua Teng dans [1] qui interpole en continu entre le pire des cas et analyses de cas moyen d'algorithmes. Ce n'est pas exactement la caractérisation discutée ci-dessus, mais elle capture le même concept, et je l'ai trouvé intéressant.

[1] Spielman, Daniel A. et Shang-Hua Teng. "Analyse lissée des algorithmes: pourquoi l'algorithme simplex prend généralement du temps polynomial." Journal de l'ACM (JACM) 51, no. 3 (2004): 385-463.

• Les instances SAT hautement structurées (même sur des millions de variables) peuvent souvent être résolues en pratique. Cependant, des instances SAT aléatoires proches du seuil de satisfiabilité avec même quelques centaines de variables sont toujours ouvertes (ce qui signifie, même dans la pratique, si vous générez une telle chose, vous ne saurez peut-être jamais pendant la durée de vie de l'univers si la chose que vous avez générée est satisfaisable ou non. utilisant des solveurs SAT actuels). Vous pourriez être intéressé par cette question connexe et ses réponses.

• Les trouveurs de cliques sont également étonnamment bons "en pratique"

  • En ce qui concerne les chercheurs de clique, (une partie de) l'explication est donnée par une analyse de cas moyenne des algorithmes en question.

    Voir https://www.sciencedirect.com/science/article/pii/S0166218X18300167?via%3Dihub

• La programmation entière et la programmation mixte linéaire-entier (avec quelques variables rationnelles et certaines variables entières) sont au centre de tous les départements de recherche opérationnelle, et peuvent souvent (mais pas toujours) être résolues dans la pratique

• $\mathsf{PSPACE}$$\mathsf{PSPACE}$

• $\mathsf{EXPSPACE}$

• Comme déjà souligné dans les commentaires de DW, l'isomorphisme graphique peut être résolu dans la pratique. Il est très difficile de créer des logiciels GI modernes tels que nauty, bliss, saucy, etc.

Le système de type Hindley-Milner est utilisé dans les langages de programmation fonctionnels (Haskell, SML, OCaml). L'algorithme d'inférence de type est pratiquement linéaire dans la pratique et fonctionne incroyablement bien, mais il est connu pour être DEXPTIME complet!

Un commentaire général: il n'est pas surprenant que la complexité au pire moment ne soit pas nécessairement une très bonne mesure des performances pratiques d'un algorithme. Cependant, dire que l'écart entre la théorie et la pratique rend la théorie de la complexité inutile, c'est comme dire que les nombres naturels sont un gaspillage parce que nous n'utilisons qu'une infime quantité de tous les nombres disponibles. Un philosophe célèbre a dit un jour: "L'expérience sans théorie est aveugle, mais la théorie sans expérience n'est qu'un jeu intellectuel".

Plus d'exemples, principalement des langages de programmation:

1. k-CFA (k-Control Flow Analysis) est complet en EXPTIME (Van Horn & Mairson 2008), mais les compilateurs d'optimisation de programme complet comme MLton le font quand même. Les temps de compilation sont longs, mais rarement désastreux.
2. La résolution (dynamique) de la surcharge est généralement NP-complète (Palsberg 2012). Mais alors c'est rarement un problème dans le monde réel.
3. $k$
4. La résolution SMT est généralement NP-complète, mais les solveurs SMT commerciaux (comme Z3 et CVC4) sont généralement assez performants. Je ne travaille pas directement avec les solveurs SMT, mais j'ai utilisé indirectement Z3 de Liquid Haskell et Dafny, et les temps de vérification semblent OK.
5. Le problème de décision pour l'arithmétique de Presburger est vraiment complexe (Fischer et Rabin 1974), mais l'algorithme de décision de Bill Pugh, le test Omega (Pugh 1991), fonctionne généralement dans un temps polynomial d'ordre faible.

$O$$n$$n$

Les références:

[1] David Van Horn et Harry G. Mairson. 2008. Décider que kCFA est terminé pour EXPTIME. Dans les Actes de la 13ème Conférence Internationale ACM SIGPLAN sur la Programmation Fonctionnelle (ICFP '08). ACM, New York, NY, USA, 275-282.

[2] http://web.cs.ucla.edu/~palsberg/paper/dedicated-to-kozen12.pdf

[3] MJ Fischer et MO Rabin. 1974. COMPLEXITÉ SUPER-EXPONENTIELLE du PRESBURGER ARITHMETIC. Rapport technique. Massachusetts Institute of Technology, Cambridge, MA, États-Unis.

[4] William Pugh. 1991. Le test Omega: un algorithme de programmation entier rapide et pratique pour l'analyse de dépendance. Dans les Actes de la Conférence ACM / IEEE de 1991 sur le Supercalcul (Supercomputing '91). ACM, New York, NY, USA, 4-13.

la formation de réseaux de neurones à l'aide de méthodes de descente de gradient s'est également avérée être un problème très difficile à résoudre. https://www.cs.utexas.edu/~klivans/crypto-hs.pdf mais est généralement résoluble en pratique.