L'origine des termes calcul / algorithme «efficace» et «faisable»

Je voudrais connaître l'histoire de ces deux termes: " efficace ", " faisable ".

Qui les a utilisés pour le calcul / les algorithmes la première fois? (au sens moderne de ces termes, c'est-à-dire du 20e siècle). Comment sont-ils devenus courants? Comment ces deux termes ont-ils commencé à être utilisés comme synonymes?

Je sais que Cobham a utilisé le terme «faisable» dans l'énoncé de sa thèse qui était associé à la calculabilité polynomiale du temps. Mais y a-t-il une référence antérieure? Il ne semble pas y avoir de référence explicite à ces termes dans la lettre de Godel à von Neumann . Je n'ai trouvé aucun article connexe antérieur à 1960 (à l'aide de Google Scholar ).

Un autre point intéressant est que le titre de l'article de Cobham de 1965 est "La difficulté de calcul intrinsèque des fonctions". Quand la "complexité informatique" a-t-elle remplacé la "difficulté informatique"?

Je ne connais pas les termes «efficace» et «faisable». Étant donné que ces termes, même aujourd'hui, n'ont pas de signification technique précise, je soupçonne que l'histoire de leur utilisation se révélera trouble, tout comme l'histoire de la plupart des mots dans la plupart des langues est trouble.

«Complexité informatique» est un terme plus intéressant. Avec l'aide de MathSciNet, je trouve que Juris Hartmanis semble avoir été le premier à le populariser. Le célèbre article de Hartmanis et Stearns de 1965 utilise le terme dans le titre, mais même avant cela, la revue mathématique de Hartmanis de l'article de Michael Rabin «Calcul en temps réel» ( Israel J. Math. 1 (1963), 203-211) dit:

Ce résultat est très instructif et apporte de nouvelles techniques à la théorie émergente de la complexité de calcul des séquences et fonctions récursives. Cette théorie s'intéresse principalement à la classification des problèmes calculables par leur degré de difficulté de calcul, l'étude des propriétés de ces classes de complexité, leur relation entre elles et leur dépendance vis-à-vis des dispositifs informatiques (abstraits).

Notez que Rabin lui-même n'utilise pas le terme «complexité de calcul» dans cet article.

MathSciNet révèle également quelques revues antérieures qui utilisent le terme «complexité de calcul», mais celles-ci semblent être des événements spontanés et sporadiques.

Une autre expression à considérer est "exactement résoluble", qui provient de la physique statistique et correspond également à nos notions actuelles d'efficacité / faisabilité. L'introduction dans cet article contient une belle description historique de cette phrase avec de nombreuses références.

Ce n'est pas exactement ce que vous avez demandé, mais c'est trop long pour un commentaire.

La plus ancienne référence explicite que je connaisse à un algorithme irréalisable se trouve dans Mémoire sur les conditions de résolubilité des équations par radicaux d' Évariste Galois , écrit en 1830:

Si maintenant vous me donnez une équation que vous aurez choisi à votre gré et que vous voulez connaître si elle est ou non soluble par radicaux, je n'aurais rien à y faire que de vous indiquer le moyen de répondre à votre question, sans vouloir chargeur ni moi ni personne de la faire. En un mot les calculs sont impraticables.

[Maintenant, si vous me donnez une équation que vous avez choisie à votre discrétion et que vous voulez savoir si elle est ou non résoluble par les radicaux, je n'ai qu'à vous indiquer la méthode nécessaire pour répondre à votre question, sans vouloir me faire ou quelqu'un d'autre le réalise. En un mot, les calculs ne sont pas pratiques .]

Bien qu'il soit vrai que l'algorithme de Galois ne fonctionne pas en temps polynomial, Galois signifiait clairement quelque chose de beaucoup moins précis. C'est aussi la plus ancienne référence que je connaisse qui considère la simple existence d'un algorithme significatif en soi.

Comme le mentionne Niel de Beaudrap dans les commentaires, Gauss a déjà discuté de (in) l'efficacité des algorithmes pour les tests de primalité dans ses 1801 Disquisitiones Arithmeticae , près de 30 ans avant Galois. Pour être complet, voici le passage pertinent de l'article 329:

Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales restrictas esse, vel tam operosas et prolixas , ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limites non excedunt, ie pro quibus methodi artificiales supervacuae sunt, calculatoriam etiam exercitati fatigent, ad maiores autem plerumque vix applicari possint. ... ceterum in problematis natura fundatum est, ut methodi quaecunquecontinuo prolixiores evadant, quo maiores sunt numeri, ad quos demandeurur; attamen pro methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim per secundam felici semper successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est, qui secundum omnes methodos hactenus indasili intolérables, exigeants.

[Néanmoins, nous devons avouer que toutes les méthodes qui ont été proposées jusqu'à présent sont soit limitées à des cas très particuliers, soit si laborieuses et prolixes que même pour des nombres qui ne dépassent pas les limites des tableaux construits par des hommes estimables, c'est- à- dire pour des nombres qui ne le sont pas. nécessitent des méthodes ingénieuses, ils essaient la patience même de la calculatrice la plus pratiquée. Et ces méthodes peuvent difficilement être utilisées pour de plus grands nombres. ... C'est dans la nature du problème que toutLa méthode deviendra plus prolixe à mesure que les nombres auxquels elle est appliquée augmentent. Néanmoins, dans les méthodes suivantes, les difficultés augmentent assez lentement, et les nombres à sept, huit, voire plus de chiffres ont été traités avec succès et rapidité au-delà des attentes, en particulier par la deuxième méthode. Les techniques qui étaient auparavant connues nécessiteraient un travail intolérable même pour la calculatrice la plus infatigable .]

Modifier: réponse réécrite

Comment est-il devenu courant? probablement en diffusant l'idée de comparer les nouvelles recherches avec les anciennes en termes de performances, en supposant que la création de nouvelles idées est plus difficile.