We don't know whether every problem whose answer is easy to check is also easy to solve

The problem

Checking a finished Sudoku takes seconds; solving one from scratch can take far longer — and nobody has proved that this gap is real. Thousands of practically vital problems, from routing trucks to folding proteins, share one shocking property: a fast method for any single one of them would crack them all. Nearly everyone believes P ≠ NP, that finding truly is harder than checking, yet half a century of effort has not produced a proof — and researchers have even proved theorems showing that whole categories of known proof techniques can never settle the question.

Why it matters

If P = NP with a practical algorithm, most modern encryption would collapse, while optimization, drug design, and even the search for mathematical proofs would become vastly easier — the world would change overnight. A proof that P ≠ NP would put the security of cryptography and the genuine hardness of thousands of everyday problems on solid ground for the first time.

Progress so far

• 1971Stephen Cook formally poses the problem; Leonid Levin arrives at it independently in the USSR
• 1975Baker, Gill and Solovay prove the 'relativization' barrier: whole families of techniques cannot resolve the question
• 1993Razborov and Rudich formulate the 'natural proofs' barrier, ruling out another broad class of attacks
• 2008Aaronson and Wigderson show 'arithmetization' techniques are also insufficient

References

1. Clay Mathematics Institute — official Millennium Prize problem page; status: unsolved
2. Wikipedia — history, barrier theorems, and refuted claimed solutions