Simon Willison’s Weblog

Computational complexity

The Computational Complexity Web Log (via Kottke):

This is the first of a long series of posts giving an informal introduction to computational complexity.

Computational complexity theorists try to determine which problem are efficiently solvable on a computer. This sentence already leads to many questions: What is a problem? What is efficiently solvable? Let us first start off with a truly basic question, what is a computer?

Great stuff for computer science students—I wish I’d had this 6 months ago when complexity came up in my programming course.

This is Computational complexity by Simon Willison, posted on 18th September 2002.

Next: RSS2 modules

Previous: Returning

Previously hosted at http://simon.incutio.com/archive/2002/09/18/computationalComplexity