P versus NP problem

The P versus NP problem asks whether two fundamental classes of computational problems are equivalent—one of the deepest unsolved questions in Mathematics and Computer Science.

P (Polynomial time) contains problems solvable quickly—meaning a Computer can find an answer in time proportional to some polynomial of the input size. NP (Nondeterministic Polynomial time) contains problems whose solutions can be verified quickly, even if finding them seems hard.

The puzzle: if verification is fast, is discovery also fast? Intuitively, it feels easier to check a solution than to find one. Yet nobody has proven this intuition correct. A Diagram of a solved sudoku confirms instantly; solving it from scratch demands search.

If P = NP, algorithms exist to solve every verifiable problem efficiently—revolutionizing Cryptography, optimization, and Statistical inference. Most mathematicians believe P ≠ NP, meaning some problems resist rapid solution despite rapid verification.

The Clay Mathematics Institute offers one million dollars for a proof either way. This problem sits at the boundary between what we can check and what we can compute, embodying fundamental limits of Efficiency and knowledge itself.

Related

Algorithm, Cryptography, Computational Complexity, NP-Complete Problems, Turing Machine, Clay Mathematics Institute