Can a Computer Solve Every Puzzle? The 50-Year Fight Over P vs. NP

The Lock with a Hundred Wheels

Imagine you have a lock with 100 numbered wheels, each with 10 digits. To open it you must find the one combination that clicks. You start turning the wheels one by one. After a minute you realize the problem: there are 10¹⁰⁰ possible combinations — more than there are atoms in the universe. If you checked a billion guesses every second, you would still need more time than the universe has existed.

That kind of lock isn’t just a nightmare for you. It’s exactly the kind of puzzle computer scientists lose sleep over. They want to know: which problems can be solved quickly, which ones are practically impossible, and is there a hard line between them? The search for an answer has produced one of the most famous open questions in all of mathematics and computer science — the problem called P versus NP.

The story begins not with locks but with a simple idea: how do you measure whether a problem is easy or hard?

Two Kinds of “Fast” and “Forever”

In the 1960s, researchers invented a way to rank problems by difficulty. They counted how many steps a computer would need as the problem got bigger. Suppose you have a list of (n) numbers and you want to sort them. Good algorithms take about (n \log n) steps. If you double the list, the time grows only a little more than double. Computer scientists call this polynomial time — the number of steps grows roughly like (n^k) for some fixed (k). Problems like sorting are in the class called P (polynomial time).

But some problems are far nastier. One way to solve the lock puzzle is brute force: test every possible combination. If the number of wheels is (n), the number of combinations grows like (2^n) (if we think in bits). Double the wheels, and the search time squares. That’s called exponential time. Even for modest (n), exponential time quickly becomes useless — the numbers outrun any computer we will ever build.

Alan Cobham and Jack Edmonds, working independently in 1965, proposed a powerful rule of thumb: a problem is feasibly computable — practical to solve — exactly when a polynomial-time algorithm exists for it. If the best algorithm can only guarantee exponential time, the problem is intractable. This idea is now called the Cobham‑Edmonds Thesis, and it’s the heartbeat of complexity theory.

But right away, a puzzle appeared. Some problems look impossible to solve in polynomial time, yet are suspiciously easy to check once you are handed an answer. And that changes everything.

The Problem Inspector: When Checking Is Easy but Solving Is Hard

Let’s look at the famous SAT problem. You are given a logical formula built from variables that can be either true or false, like

(P OR Q) AND (NOT P OR R) AND (NOT Q OR NOT R)

The question is: does there exist an assignment of true/false to P, Q, R that makes the whole formula true? If you try all possibilities for a formula with 100 variables, you need to check (2^{100}) rows — again, exponential. But if I hand you a candidate assignment, you can check whether it works in a snap. The problem of checking is easy, even though finding the assignment seems hard.

Problems like SAT belong to a class called NP (nondeterministic polynomial time). The name sounds scary, but the core idea is simple: a problem is in NP if, whenever the answer is “yes,” there is some short certificate (like the correct assignment) that a computer can verify in polynomial time. NP doesn’t mean “not polynomial” — it means “checkable fast when someone gives you a lucky guess.”

Now the huge question: is NP really bigger than P? Or does every problem that can be checked quickly also admit a fast way to find the solution? That’s the P versus NP problem — and it has stumped everyone for over fifty years.

The Hardest Puzzles of All: NP‑Complete Problems

In 1971 Stephen Cook proved something remarkable. He showed that if you could solve SAT in polynomial time, then every problem in NP could also be solved in polynomial time. SAT is NP‑complete — it is one of the hardest problems in NP, so hard that it encodes all the others. Richard Karp then found 21 more NP‑complete problems, including route planning (the Traveling Salesman), game strategies, and puzzle games. Today thousands of problems are known to be NP‑complete.

Here’s the magic: all NP‑complete problems stand or fall together. If someone discovers a polynomial algorithm for one of them, then P = NP, and every NP problem becomes easy. If, on the other hand, any NP‑complete problem really is intractable, then P ≠ NP, and a permanent gap exists between solving and checking.

Most mathematicians and computer scientists are convinced P ≠ NP. The strongest evidence is simple: despite decades of intense effort, nobody has found a fast algorithm for any NP‑complete problem. Yet no one has been able to prove that such an algorithm cannot exist. The status of P versus NP is still an open question — one of the seven “Millennium Prize” problems, with a $1,000,000 reward for a correct solution.

Why You Should Care About P ≠ NP

This isn’t just a curiosity for mathematicians. The world’s digital security depends on the belief that certain problems are hard. When you buy something online, your credit card number is protected by a code based on the difficulty of factoring large numbers into primes. The factoring problem is believed to be outside P, though it’s not yet known to be NP‑complete. If someone proved P = NP and found a fast factoring algorithm, much of modern cryptography would collapse overnight.

There’s a deeper, philosophical side too. In 1956 the logician Kurt Gödel wrote a letter to John von Neumann. He noted that if a computer could quickly decide whether a mathematical statement has a short proof, then “the mental effort of the mathematician in the case of yes‑or‑no questions could be completely replaced by machines.” In other words, if P = NP, a machine could not only verify our reasoning but could discover it — and creativity might be reduced to a computation.

Of course, we don’t know whether that will happen. The current guess is that P ≠ NP, which means there are genuine barriers that even the fastest computers cannot overcome. The boundary between the quickly checkable and the quickly solvable may be one of the deepest features of our mathematical universe — and it’s still waiting for someone to finally prove it.

Think about it

1. If a computer could solve every puzzle in a few seconds, would there still be any point in humans doing puzzles?
2. Some people worry that if P = NP, all secret codes would break. Does that mean we should stop looking for faster algorithms, or should we keep exploring anyway?
3. If you had a machine that could instantly check whether a proof of any math problem exists, would you still enjoy discovering new mathematics?