Quais são os primeiros trabalhos de ciência da computação que usaram complexidade de tempo assintótica?

Quando o O grande foi usado pela primeira vez na ciência da computação e quando se tornou padrão? A página da Wikipedia cita Knuth, Big Omicron e Big Omega And Big Theta , SIGACT de abril a junho de 1976, mas o início desse artigo diz

A maioria de nós se acostumou à idéia de usar a notação para representar qualquer função cuja magnitude seja delimitada por tempos constantes , para todo o grande .f ( n ) $O(f(n))$$f(n)$$n$

Esta citação indica que a ideia e a notação já estavam em uso comum.

A página da Wikipedia também cita trabalhos de matemática do final do século XIX e início do século XX, mas isso não responde à pergunta. Em particular, ouvi pesquisadores que estavam na época (nos anos 60 e 70, e não no final de 1800) dizer que, quando a análise assintótica foi usada pela primeira vez, algumas pessoas recuaram, dizendo que o tempo do relógio de parede era uma métrica melhor. No entanto, ninguém com quem conversei pode citar os documentos específicos que tiveram uma reação desse tipo e eu gostaria de encontrar evidências que possam confirmar ou negar essas histórias.

com questões de história, normalmente existem nuances sutis e não é fácil determinar um artigo em particular que introduza um conceito específico, porque ele tende a se espalhar por muitos colaboradores e às vezes é redescoberto de forma independente quando referências precoces obscuras não são necessariamente divulgadas (as idéias fundamentais são assim) . mas a história é basicamente algo assim: a notação de Landau é um antigo formalismo matemático (1894 / Bachman) [1] que foi importado para o CS como um "conceito-chave" no início dos anos 1970. em meados da década de 1970, isso foi um pouco aceito como na referência de Knuth e o próprio Knuth estava envolvido na divulgação desse conceito.

Curiosamente, sua importação para o CS provavelmente estava intimamente relacionada às distinções P vs NP vs Exptime, descobertas no início da década de 1970, que foram altamente influentes / anunciadas no campo. foi Cobham / Edmonds quem começou a definir a classe P no início dos anos 70. [3] houve provas iniciais sobre Exptime e Expspace de Stockmeyer / Meyer. [2] o teorema de Cook-Levin [4] (1971) mostrou a relevância central do tempo P vs NP, imediatamente apoiado por Karp [5] (1972).

um dos primeiros matemáticos que trabalhava na teoria dos números, mas também no limite da ciência da computação era Pocklington. como em [3] aponta:

No entanto, HC Pocklington, em um artigo de 1910, [11] [12] analisou dois algoritmos para resolver congruências quadráticas e observou que um levou tempo "proporcional à potência do logaritmo do módulo" e o contrastou com outro que levou tempo. proporcional "ao módulo em si ou à sua raiz quadrada", estabelecendo assim uma distinção explícita entre um algoritmo executado em tempo polinomial versus um que não.

Outro pioneiro na análise da complexidade de algoritmos baseados em máquina para a teoria dos números, ou seja, fatoração, foi Derrick Lehmer, professor de matemática na Universidade da Califórnia, Berkeley, e construiu / analisou "algoritmos" de fatoração (implementações baseadas em peneiras) desde a década de 1920 e é possível que ele tenha descrito algo como complexidade computacional por fator informal de maneira informal. [6]

ainda outro caso é uma carta "perdida" de 1956 de Godel a von Neumann, falando sobre medições de complexidade dos passos f (n) de uma máquina para encontrar provas do tamanho n . [7]

[1] História da notação Big O / wikipedia

[2] Problemas com palavras que exigem tempo exponencial. / Stockmeyer, Meyer (1973)

[3] História da classe de tempo P / wikipedia

[4] Teorema de Cook-Levin / wikipedia

[5] Karps 21 NP complete problems / wikipedia

[6] Máquina de fatoração Lehmer / peneira / wikipedia

[7] Godels perdeu a carta / RJLipton