More introduction to computation, Turing Machines and time complexity. Defined P and briefly NP.
Papers mentioned:
Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem
Where he defines the Turing machine. Section 9 is worth reading where he basically defends his thesis that this model defines computability.
Juris Hartmanis and Richard Stearns, On the Computational Complexity of Algorithms
This paper started the field of computational complexity. It's major insight was to consider resources like time and memory as a function of the input size.
Jack Edmonds, Paths, Trees and Flowers
This paper gives a polynomial-time algorithm for graph matching and argues that polynomial-time is a reasonable stand in for efficient computation.
Alan Cobham, The Intrinsic Computational Difficulty of Functions
Cobham gave a similar argument for polynomial time.
