História dos Modelos Computacionais

Antes de a pesquisa propriamente dita explicitamente dedicada à complexidade dos problemas algorítmicos começar, os numerosos fundamentos foram estabelecidos por vários pesquisadores. O mais influente entre estes foi a definição das máquinas de Turing por Alan Turing em 1936, que acabou por ser uma noção muito robusta e flexível de computador.
Fortnow & Homer (2003) datam o início dos estudos sistemáticos em complexidade computacional com o importante artigo "On the Computational Complexity of Algorithms" de Juris Hartmanis e Richard Stearns (1965), que estabeleceu as definições de complexidade de tempo e de espaço e provou os teoremas de hierarquia.
De acordo com Fortnow & Homer (2003), trabalhos anteriores que estudaram problemas solucionáveis por máquinas de Turing com recursos específicos limitados inclui a definição de John Myhill de autômatos linearmente limitados (Myhill 1960), o estudo de Raymond Smullyan sobre conjuntos rudimentares (1961), assim como o artigo de Hisao Yamada  sobre computação em tempo real (1962). Um pouco mais cedo, Boris Trakhtenbrot (1956), um pioneiro no campo da URSS, estudou outra medida específica de complexidade. Como lembra ele:

Contudo, [meu] interesse inicial [na teoria dos autômatos] era cada vez mais posto de lado em detrimento à complexidade computacional, uma excitante fusão de métodos combinatoriais, herdada da teoria da comutação, com o arsenal conceitual da teoria de algoritmos. Essas ideias me ocorreram antes, em 1955, quando eu cunhei o termo "função de sinalização", que hoje é comumente conhecido como "medida de complexidade". —Boris Trakhtenbrot

From Logic to Theoretical Computer Science – An Update. In: Pillars of Computer Science, LNCS 4800, Springer 2008.

Em 1967, Manuel Blum desenvolveu uma teoria da complexidade axiomática com base em seus axiomas e provou um resultado importante, o então chamado, teorema da aceleração de Blum (speed-up theorem). O campo realmente começou a florescer quando o pesquisador norte-americano Stephen Cook e, trabalhando independentemente, Leonid Levin na URSS, provaram que existem importantes problemas praticáveis que são NP-completos. Em 1972, Richard Karp partiu desta ideia e deu um salto à frente com seu artigo histórico, "Reducibility Among Combinatorial Problems", no qual ele mostrou que 21 diferentes problemas de combinatória e problemas teóricos de grafos, famosos por sua intratabilidade computacional, são NP-completos.