VII · Computational complexity

NP-completeness

What it is

A problem is NP-complete if every NP problem reduces to it in polynomial time. Cook-Levin (1971): SAT is NP-complete. Karp (1972): 21 problems are.

Where it lives

TSP, graph colouring, knapsack, vertex cover, scheduling — most "looks like" NP-hard problems are.

The key insight

A polynomial-time algorithm for any NP-complete problem would solve all of them. Reductions are how you prove your problem is hard without designing a new algorithm.

More in Computational complexity

P vs NP P: problems solvable in polynomial time. NP: problems whose solutions … 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 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 X Hamming codes Coding theory

← All foundations