VII · Computational complexity

P vs NP

What it is

P: problems solvable in polynomial time. NP: problems whose solutions can be verified in polynomial time. The conjecture P ≠ NP is the most consequential open problem in computing.

Where it lives

Underpins all of cryptography, optimisation theory, and the very notion of "this problem is hard".

The key insight

A million-dollar Clay Prize is open for either direction. Most cryptographers bet P ≠ NP, but no proof exists.

More in Computational complexity

NP-completeness A problem is NP-complete if every NP problem reduces to it in polynomi… Approximation algorithms When exact solutions are too expensive, find an answer guaranteed with… Reductions Show your problem is at least as hard as a known hard problem by mappi…

Across the foundations

VIII Central Limit Theorem Statistics & inference VIII Hypothesis testing & p-values Statistics & inference VIII Confidence intervals Statistics & inference VIII Power & sample size Statistics & inference IX Eigenvalues & eigenvectors Linear algebra IX Singular Value Decomposition Linear algebra IX Norms & inner products Linear algebra IX Matrix multiplication complexity Linear algebra

← All foundations