Why are some puzzles quick to check but, as far as we know, slow to solve?

Some puzzles have a strange split personality: checking a finished answer is instant, but finding that answer in the first place can be brutally slow. Sudoku is the textbook case. If someone hands you a completed grid, you can confirm it's correct in moments, just scan each row, column, and block. But the general problem of solving Sudoku puzzles on larger and larger grids is known to be NP-complete, meaning it belongs to the hardest class of problems whose solutions can be verified quickly, with no known shortcut for finding them.

Algorithms like brute-force backtracking can crack a normal 9x9 Sudoku efficiently enough, but as the grid size grows, a combinatorial explosion kicks in, and the number of possibilities to check balloons out of control. That's the defining trait of NP-complete problems in general: although a solution can be verified quickly, there is no known way to find one quickly, and the time required by any known algorithm increases rapidly as the problem grows.

Whether that's a permanent law of mathematics or just a gap in our cleverness is a major unsolved problem in theoretical computer science, called the P versus NP problem. It asks, informally, whether every problem whose answer can be checked quickly can also be solved quickly. Nobody knows. It's considered so important that it's one of seven Millennium Prize Problems, each carrying a $1,000,000 reward for the first correct solution.

The suspicion that verifying and solving are fundamentally different jobs goes back further than you'd expect. In 1955, the mathematician John Nash wrote a letter to the National Security Agency speculating that cracking a sufficiently complex code should take exponentially longer as the code's key gets longer, Since a proposed key can be checked quickly, proving Nash right would imply what is now called P ≠ NP. Nobody has managed it yet.