Pochodzenie terminów „wydajne” i „wykonalne” obliczenia / algorytmy

Chciałbym wiedzieć o historii tych dwóch terminów: „ skuteczny ”, „ wykonalny ”.

Kto zastosował je po raz pierwszy w obliczeniach / algorytmach? (w nowoczesnym znaczeniu tych terminów, tj. XX wieku). Jak stały się głównym nurtem? Jak te dwa terminy zaczęły być używane jako synonimy?

Wiem, że Cobham użył terminu „wykonalny” w wypowiedzi swojej tezy, która związana była z wielomianowym obliczaniem czasu. Ale czy istnieje wcześniejsze odniesienie? Wydaje się, że nie ma wyraźnego odniesienia do tych terminów w liście Godla do von Neumanna . Nie mogłem znaleźć żadnego pokrewnego artykułu sprzed 1960 roku (używając Google Scholar ).

Innym interesującym punktem jest to, że tytuł pracy Cobhama z 1965 r. Brzmi: „Wewnętrzna trudność obliczeniowa funkcji”. Kiedy „złożoność obliczeniowa” zastąpiła „trudność obliczeniową”?

Nie znam terminów „wydajny” i „wykonalny”. Ponieważ te terminy nawet dzisiaj nie mają dokładnego znaczenia technicznego, podejrzewam, że historia ich użycia okaże się mroczna, podobnie jak historia większości słów w większości języków jest mroczna.

„Złożoność obliczeniowa” jest bardziej interesującym terminem. Z pomocą MathSciNet odkryłem, że Juris Hartmanis był pierwszym, który ją spopularyzował. Słynny artykuł Hartmanisa i Stearnsa z 1965 r. Używa tego tytułu w tytule, ale nawet wcześniej Matematyczny przegląd pracy Michaela Rabina w artykule „Obliczenia w czasie rzeczywistym” Michaela Rabina ( Israel J. Math. 1 (1963), 203–211) mówi:

Ten wynik jest bardzo pouczający i wnosi nowe techniki do wyłaniającej się teorii złożoności obliczeniowej sekwencji i funkcji rekurencyjnych. Teoria ta dotyczy głównie klasyfikacji problemów obliczeniowych według stopnia trudności obliczeniowej, badania właściwości tych klas złożoności, ich wzajemnych relacji i zależności od (abstrakcyjnych) urządzeń obliczeniowych.

Zauważ, że sam Rabin nie używa w tym artykule terminu „złożoność obliczeniowa”.

MathSciNet pojawia się także kilka wcześniejszych recenzji, które używają terminu „złożoność obliczeniowa”, ale wydaje się, że są to spontaniczne i sporadyczne zdarzenia.

Innym zwrotem, który należy wziąć pod uwagę, jest „dokładnie rozwiązany”, który pochodzi z fizyki statystycznej i również odpowiada naszym współczesnym wyobrażeniom o wydajności / wykonalności. Wprowadzenie do tego artykułu zawiera ładny historyczny opis tego zdania z wieloma odniesieniami.

To nie jest dokładnie to, o co prosiłeś, ale jest za długo na komentarz.

Najstarsze wyraźne odniesienie, które znam do niemożności wykonania algorytmu, znajduje się w Évariste Galois „ Mémoire sur les warunki de résolubilité des équations par radicaux” , napisanej w 1830 r .:

Jeśli utrzymujesz, że nie jesteś w stanie odpowiedzieć na pytanie, czy jesteś gotów na przyjęcie i jesteś w stanie rozwiązać problem nierozpuszczalny w radicaux, to n'aurais rien à y faire que de vous indiquer le moyen de répondre à votre question, sans vouloir ładowarka moi ni personne de la faire. En un mot les wylicza, że ​​są niewykonalne.

[Teraz, jeśli podasz mi równanie, które wybrałeś według własnego uznania i chcesz wiedzieć, czy są one możliwe do rozwiązania przez radykałów, muszę tylko wskazać ci metodę potrzebną do udzielenia odpowiedzi na twoje pytanie, bez potrzeby tworzenia siebie lub ktokolwiek inny to wykona. Jednym słowem obliczenia są niepraktyczne .]

Chociaż prawdą jest, że algorytm Galois nie działa w czasie wielomianowym, Galois wyraźnie oznaczał coś znacznie mniej precyzyjnego. Jest to również najstarsze znane mi odniesienie, które uważa, że ​​samo istnienie algorytmu jest znaczące samo w sobie.

Jak wspomina Niel de Beaudrap w komentarzach, Gauss omawiał (nie) wydajność algorytmów do testowania pierwotności w swoich 1801 Disquisitiones Arithmeticae , prawie 30 lat przed Galois. Dla kompletności oto odpowiedni fragment z artykułu 329:

Nihilominus fateri oportet, omnes methodos hucusque prolata vel ad casus vlade speciales limitas esse, vel tam operosas i prolixas , ut iam pro numeris talibus, qui tabularum a varis meritis constructarum limits non excedunt, tj. Pro quibus methodi sztuczes supervacuae suntc, kalkulator i kalkulator fatigent, ad maiores autem plerumque vix applari possint. ... Ceterum in problematis natura fundatum est, ut methodi quaecunqueContinuo prolixiores evadant, quo maiores sunt numeri, ad quos wnioskodawca; attamen pro methodis sequentibus difficultates perlente increscunt, NUMERIQUE e septem, octos vel adeo adhuc pluribus figuris constantes praesertim za secundam Felici sempre successu tractati fuerunt, omnique celeritate, quam pro tantis numeris exspectare aequum est qui secundum omnes methodos hactenus notas Laborem, Etiam calculatori indefatigabili nietolerancja, wymagająca.

[Niemniej jednak musimy wyznać, że wszystkie dotychczas zaproponowane metody są albo ograniczone do bardzo szczególnych przypadków, albo są tak pracochłonne i ciągłe, że nawet dla liczb, które nie przekraczają granic tabel skonstruowanych przez szacownych mężczyzn, tj. Dla liczb, które nie wymagają genialnych metod, próbują cierpliwości nawet najbardziej wyćwiczonego kalkulatora. Te metody nie mogą być stosowane w przypadku większych liczb. ... Jest to charakter problemu, który każdymetoda stanie się bardziej ciągła, gdy liczby, do których jest stosowana, będą rosły. Niemniej jednak w poniższych metodach trudności rosną raczej powoli, a liczby z siedmioma, ośmioma, a nawet więcej cyframi były obsługiwane z powodzeniem i szybkością przekraczającą oczekiwania, zwłaszcza drugą metodą. Techniki, które były wcześniej znane, wymagałyby pracy nie do zniesienia nawet dla najbardziej niestrudzonego kalkulatora .]

Edycja: odpowiedź napisana od nowa

Jak dostało się do głównego nurtu? prawdopodobnie poprzez rozpowszechnianie idei porównywania nowych badań ze starszymi pod względem wydajności, przy założeniu, że tworzenie nowych pomysłów jest trudniejsze.