Login
How Hard is too Hard? An Introduction to Complexity
Share
- Details
- Text
- Audio
- Downloads
- Extra Reading
Some mathematical problems can easily be solved on a computer, whilst some are probably impossible. Complexity theory is how we analyse difficulty, and one of the most famous open problems in mathematics is the question of whether P = NP: if the answer to a problem is easy to check, is the problem actually easy to solve? This lecture introduces the work of Alan Turing and other pioneers in the subject, before bringing us up-to-date with some recent progress.
Download Text
There are mathematical equations in this accompanying text which prevent us from embedding the text in this page. Please download the file above.
References and Further Reading
Scott Aaronson, Quantum Computing Since Democritus (Cambridge University Press, 2013).
William J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University Press, 2012).
Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible(Princeton University Press, 2013).
Dennis Shasha, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists (first published 1995; Springer, 2008).
This event was on Mon, 11 May 2026
Support Gresham
Gresham College has offered an outstanding education to the public free of charge for over 400 years. Today, Gresham College plays an important role in fostering a love of learning and a greater understanding of ourselves and the world around us. Your donation will help to widen our reach and to broaden our audience, allowing more people to benefit from a high-quality education from some of the brightest minds.
