Der Ursprung der Begriffe "effiziente" und "machbare" Berechnung / Algorithmus

Ich würde gerne etwas über die Geschichte dieser beiden Begriffe erfahren: " effizient ", " machbar ".

Wer hat sie zum ersten Mal für Berechnungen / Algorithmen verwendet? (im modernen Sinne, dh 20. Jahrhundert). Wie sind sie zum Mainstream geworden? Wie wurden diese beiden Begriffe als Synonyme verwendet?

Ich weiß, dass Cobham den Begriff "machbar" in der Aussage seiner These verwendet hat, die sich auf die polynomielle Zeitberechnungsfähigkeit bezieht. Aber gibt es eine frühere Referenz? In Gödels Brief an von Neumann scheint es keinen ausdrücklichen Hinweis auf diese Begriffe zu geben . Ich konnte keinen ähnlichen Artikel vor 1960 finden (mit Google Scholar ).

Ein weiterer interessanter Punkt ist, dass der Titel von Cobhams Arbeit von 1965 "Die intrinsische Rechenschwierigkeit von Funktionen" lautet . Wann hat "Rechenkomplexität" "Rechenschwierigkeiten" ersetzt?

Ich kenne die Begriffe "effizient" und "machbar" nicht. Da diese Begriffe auch heute noch keine genaue technische Bedeutung haben, vermute ich, dass sich die Geschichte ihrer Verwendung als trübe herausstellen wird, so wie die Geschichte der meisten Wörter in den meisten Sprachen trübe ist.

"Computational Complexity" ist ein interessanter Begriff. Mit Hilfe von MathSciNet stelle ich fest, dass Juris Hartmanis anscheinend der Erste war, der es populär machte. Die berühmte Arbeit von Hartmanis und Stearns aus dem Jahr 1965 verwendet den Begriff im Titel, aber Hartmanis 'mathematischer Aufsatz zu Michael Rabins Arbeit "Real time computation" ( Israel J. Math. 1 (1963), 203–211) besagt bereits zuvor:

Dieses Ergebnis ist sehr aufschlussreich und trägt neue Techniken zur aufkommenden Theorie der rechnerischen Komplexität rekursiver Folgen und Funktionen bei. Diese Theorie befasst sich hauptsächlich mit der Klassifizierung berechenbarer Probleme nach ihrem Schwierigkeitsgrad, der Untersuchung der Eigenschaften dieser Komplexitätsklassen, ihrer Beziehung zueinander und ihrer Abhängigkeit von den (abstrakten) Rechengeräten.

Beachten Sie, dass Rabin selbst in diesem Artikel den Begriff "Komplexität der Berechnungen" nicht verwendet.

MathSciNet zeigt auch einige frühere Übersichten, in denen der Begriff "rechnerische Komplexität" verwendet wird, bei denen es sich jedoch anscheinend um spontane und sporadische Ereignisse handelt.

Ein weiterer zu berücksichtigender Ausdruck ist "genau lösbar", der aus der statistischen Physik stammt und auch unseren heutigen Vorstellungen von effizient / machbar entspricht. Die Einleitung in diesem Artikel enthält eine schöne historische Beschreibung dieses Satzes mit vielen Referenzen.

Dies ist nicht genau das, wonach Sie gefragt haben, aber es ist zu lang für einen Kommentar.

Der älteste explizite Hinweis, den ich kenne, dass ein Algorithmus nicht ausführbar ist , befindet sich in Évariste Galois ' 1830 verfasstem Mémoire sur les conditions de résolubilité des équations par radicaux :

Die Wartung ist nur dann möglich, wenn Sie eine Wahl treffen, bei der Sie eine Frage haben, die Sie nicht lösen können Ladegerät ni moi ni personne de la faire. En un mot les calculs sont undurchführbar.

[Wenn Sie mir nun eine Gleichung geben, die Sie nach eigenem Ermessen gewählt haben und wissen möchten, ob sie durch Radikale lösbar ist oder nicht, muss ich Ihnen nur die Methode angeben, die zur Beantwortung Ihrer Frage erforderlich ist, ohne mich oder zu machen jemand anderes führt es aus. Mit einem Wort, die Berechnungen sind unpraktisch .]

Obwohl es stimmt, dass der Algorithmus von Galois nicht in polynomieller Zeit abläuft, bedeutete Galois eindeutig etwas viel weniger Genaues. Dies ist auch die älteste mir bekannte Referenz, die die bloße Existenz eines Algorithmus für sich betrachtet .

Wie Niel de Beaudrap in den Kommentaren erwähnt, hat Gauß bereits in seinen Disquisitiones Arithmeticae von 1801 , fast 30 Jahre vor Galois, die (In-) Effizienz von Algorithmen zur Prüfung der Primalität diskutiert . Der Vollständigkeit halber hier die relevante Passage aus Artikel 329:

Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales, vel tam operosas et prolixas , ut iam pro numeris talibus, qui tabularum und varis meritis constructarum limites non excedunt, dh pro quibus methodi artificiales supervacuae sunt, calculatoris etiam ermüdend, ad maiores autem plerumque vix applicari possint. ... Ceterum in problematis natura fundatum est, ut methodi quaecunquecontinuo prolixiores evadant, quo maiores sunt numeri, ad quos applicantur; attamen pro Methodis sequentibus difficultates perlente increscunt, numerique e septem, octos vel adeo adhuc pluribus figuris constantes praesertim pro secundam felici semper successu tractati fuerunt, omnique celeritate, quam pro Tantis numeris exspectare aequum est, qui secundum omnes methodos hactenus notas laborem, etiam calculatori indefatigabili intolerabilem, requirerent.

[Trotzdem müssen wir zugeben, dass alle bisher vorgeschlagenen Methoden entweder auf sehr spezielle Fälle beschränkt sind oder so aufwendig und prolixartig sind, dass selbst für Zahlen, die die Grenzen von Tabellen, die von schätzbaren Männern erstellt wurden, nicht überschreiten, dh für Zahlen, die dies nicht tun erfordern ausgeklügelte Methoden, sie versuchen die Geduld selbst des geübten Taschenrechners. Und diese Methoden sind bei größeren Stückzahlen kaum zu gebrauchen. ... Es liegt in der Natur des Problems, dass jederMethode wird mehr prolix, wenn die Zahlen, auf die es angewendet wird, größer werden. Nichtsdestotrotz nehmen bei den folgenden Methoden die Schwierigkeiten ziemlich langsam zu und Zahlen mit sieben, acht oder noch mehr Stellen wurden mit Erfolg und Geschwindigkeit über die Erwartungen hinaus behandelt, insbesondere bei der zweiten Methode. Die Techniken, die vorher bekannt waren, würden selbst für den unermüdlichsten Taschenrechner unerträgliche Arbeit erfordern .]

Bearbeiten: Antwort neu geschrieben

Wie kam es zum Mainstream? wahrscheinlich durch die Verbreitung der Idee, neue Forschungsergebnisse in Bezug auf die Leistung mit älteren zu vergleichen, mit der Annahme, dass die Schaffung neuer Ideen schwieriger ist.