Computational complexity
18th September 2002
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.
More recent articles
- Recreating the Apollo AI adoption rate chart with GPT-5, Python and Pyodide - 9th September 2025
- GPT-5 Thinking in ChatGPT (aka Research Goblin) is shockingly good at search - 6th September 2025
- V&A East Storehouse and Operation Mincemeat in London - 27th August 2025