Colva Roney-Dougal, Professor of Pure Mathematics at the University of St Andrews, introduces computational complexity theory at Gresham College. She opens with a party seating puzzle, modeling it as a graph of vertices and edges, then traces the subject back to Alan Turing and the halting problem to show why some problems have no solution at all. From there she distinguishes solvable from efficiently solvable, explaining why polynomial time counts as tractable, and connects this to cryptography, where the hardness of factoring primes protects encrypted data. Job scheduling and backtrack search illustrate how real computers tackle NP problems in practice. The lecture builds to the P versus NP question, the million dollar Clay Millennium Prize, NP-complete problems, and a recent quasi-polynomial time breakthrough on graph isomorphism, closing with the threat quantum computing poses to current encryption schemes.