An historical overview of computational complexity is presented. Emphasis is on the fundamental issues of defining the intrinsic computational complexity of a problem and proving upper and lower bounds on the complexity of problems. Probabilistic and parallel computation are discussed.
No takes yet. Share an insight, caveat, or question.
Stephen Cook (1983) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: