Come sottolineato da Fortnow & Homer (2003), l' inizio di studi sistematici sulla complessità computazionale è attribuito al lavoro seminale "Sulla complessità computazionale degli Algoritmi" di Juris Hartmanis e Richard Stearns (1965), che ha delineato le definizioni di complessità temporale e spaziale e dimostrato i teoremi gerarchici. Inoltre, nel 1965 Edmonds definì un algoritmo "buono" come uno con tempo di esecuzione limitato da un polinomio delle dimensioni dell' ingresso.
Quale documento è comunemente considerato il bellwether inaugurare studi sistematici complessità computazionale?
Sulla complessità computazionale degli Algoritmi Sulla complessità computazionale degli Algoritmi "Sulla complessità computazionale degli Algoritmi"