Imagine you're standing in front of a locked door, holding a keyring with a million keys on it. Finding the right key by trying them one at a time could take forever. But if someone hands you a single key and says "this one opens it," you can check that claim in seconds — just put it in the lock and turn. That gap, between how hard it is to find a solution and how easy it is to check one, is the entire subject of this book.

Computer scientists have a name for problems where a good solution can be checked quickly: they're in a class called NP. And they have a name for problems where a good solution can be found quickly, from scratch, with no key handed to you in advance: that class is called P. The question "P vs NP" asks something deceptively simple: is finding always as easy as checking? Or are there problems — like our locked door — where checking a candidate answer is fast, but finding that answer in the first place is genuinely, unavoidably hard?

Almost everyone who works with computers has a gut instinct that finding is harder than checking. It's easy to verify that a Sudoku puzzle has been solved correctly — you just scan the rows, columns, and boxes. It's much harder to solve the puzzle yourself. It's easy to check that a proposed route through twenty cities is under 500 miles — just add up the distances. It's much harder to find the shortest such route among the billions of possible orderings. The open question is whether this feeling — that finding is harder than checking — is actually true in a mathematically rigorous sense, or whether it's an illusion caused by the fact that nobody has yet found the clever trick that makes finding just as fast as checking.