NP-Complete

NP-complete problems are the hardest problems in NP: they are in NP, and every problem in NP reduces to them in polynomial time.

If any NP-complete problem has a polynomial-time algorithm, then every problem in NP does (P = NP). Examples include 3-SAT and the decision version of the traveling salesman problem (does a tour of length at most $k$ exist?).

← Back to CS Glossary