Was sind die ersten Informatik-Artikel, die asymptotische Zeitkomplexität verwendeten?

Wann wurde big O zum ersten Mal in der Informatik eingesetzt und wann wurde es zum Standard? Die Wikipedia-Seite zu diesem Thema zitiert Knuth, Big Omicron und Big Omega und Big Theta , SIGACT April-Juni 1976, aber der Anfang dieses Artikels lautet

Die meisten von uns haben sich daran gewöhnt, die Notation für jede Funktion zu verwenden, deren Größe für alle großen n durch konstante Zeiten f ( n ) nach oben begrenzt ist .$O(f(n))$$f(n)$$n$

Dieses Zitat zeigt an, dass die Idee und die Notation bereits gebräuchlich waren.

Die Wikipedia-Seite zitiert auch mathematische Artikel aus den späten 1800er und frühen 1900er Jahren, aber das beantwortet die Frage nicht ganz. Insbesondere habe ich gehört, dass Forscher, die es damals gab (in den 60er und 70er Jahren, nicht im späten 19. Jahrhundert), sagten, dass bei der ersten Verwendung der asymptotischen Analyse einige Leute zurückgedrängt wurden und sagten, die Zeit der Wanduhr sei eine bessere Metrik. Jedoch kann niemand, mit dem ich gesprochen habe, die spezifischen Veröffentlichungen zitieren, die einen solchen Rückstoß erfahren haben, und ich möchte Beweise finden, die diese Geschichten bestätigen oder leugnen können.

Bei Fragen zur Geschichte gibt es normalerweise subtile Nuancen, und es ist nicht einfach, ein bestimmtes Papier zu bestimmen, das ein bestimmtes Konzept eingeführt hat, da es sich in der Regel über viele Mitwirkende erstreckt und manchmal selbstständig wiederentdeckt wird, wenn verdeckte frühe Referenzen nicht unbedingt verbreitet werden (grundlegende Ideen sind wie diese). . Aber die Geschichte geht im Grunde in etwa so: Die Landau-Notation ist ein alter mathematischer Formalismus (1894 / Bachman) [1], der um die frühen 1970er Jahre als "Schlüsselbegriff" in CS eingeführt wurde. Mitte der 1970er Jahre wurde dies in gewisser Weise akzeptiert, wie in Ihrer Knuth-Referenz, und Knuth selbst war an der Verbreitung dieses Konzepts beteiligt.

Interessanterweise war sein Import in CS wahrscheinlich eng mit den zu Beginn der 1970er Jahre aufgedeckten Unterschieden zwischen P vs NP vs Exptime verbunden, die auf diesem Gebiet einen großen Einfluss hatten. es war Cobham / Edmonds, der Anfang der 1970er Jahre damit begann, die Klasse P zu definieren. [3] Es gab frühe Beweise über Exptime und Expspace von Stockmeyer / Meyer. Das Cook-Levin-Theorem [4] (1971) zeigte die Kernrelevanz von P gegen NP-Zeit, die unmittelbar von Karp [5] (1972) unterstützt wurde.

Ein früher Mathematiker, der in der Zahlentheorie, aber auch am Rande der Informatik arbeitete, war Pocklington. wie in [3] heißt es:

In einem Aufsatz von 1910 analysierte HC Pocklington [11] [12] zwei Algorithmen zum Lösen quadratischer Kongruenzen und stellte fest, dass eine Zeit "proportional zu einer Potenz des Logarithmus des Moduls" und eine andere Zeit "dauerte" proportional "zum Modul selbst oder seiner Quadratwurzel", wodurch explizit zwischen einem Algorithmus, der in Polynomialzeit lief, und einem Algorithmus, der nicht lief, unterschieden wird.

Ein weiterer Pionier bei der Analyse der Komplexität maschinenbasierter Algorithmen für die Zahlentheorie, das heißt das Faktorisieren, war Derrick Lehmer, Professor für Mathematik an der University of California in Berkeley, der bereits in den 1920er Jahren Factoring-Algorithmen (siebbasierte Implementierungen) gebaut und analysiert hat und es ist möglich, dass er so etwas wie rechnerische Komplexität in informeller Weise beschrieben hat. [6]

Ein weiterer Fall ist ein "verlorener" Brief von Godel an von Neumann aus dem Jahr 1956, in dem es um Komplexitätsmessungen der Schritte f (n) einer Maschine geht, um Beweise der Größe n zu finden . [7]

[1] Geschichte der Big O-Notation / Wikipedia

[2] Wortprobleme, die exponentielle Zeit erfordern. / Stockmeyer, Meyer (1973)

[3] P Zeitklassenverlauf / Wikipedia

[4] Cook-Levin-Satz / Wikipedia

[5] Karps 21 NP vollständige Probleme / Wikipedia

[6] Lehmer Factoring Machine / Sieb / Wikipedia

[7] Godels verlor Brief / RJLipton