NP-completeness

NP-completeness classifies decision problems that belong to NP and are at least as hard as every problem in NP under polynomial-time reductions.

P (complexity): The class of decision problems solvable by a deterministic algorithm in polynomial time. P versus NP asks whether every efficiently verifiable problem is also efficiently solvable.
NP-hardness: A property of problems to which every problem in NP can be reduced in polynomial time. This is the hardness half of the definition; it does not require the problem itself to lie in NP.
Traveling salesman problem: The optimization problem of finding a shortest tour that visits each city once and returns to its start. Its decision version is NP-complete, connecting route planning to the class.
P versus NP problem: The open question of whether every problem with efficiently verifiable solutions also has an efficient algorithm. A polynomial-time algorithm for any NP-complete problem would imply P equals NP.
NP (complexity): The class of decision problems whose yes-instances have certificates verifiable in polynomial time. NP-completeness concerns the hardest problems inside this class.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete. It supplies the first NP-complete problem, enabling reductions to establish hardness for others.
Vertex cover: The problem of finding a smallest set of graph vertices touching every edge. Its decision version is a familiar NP-complete graph problem.
Exponential time hypothesis: The conjecture that 3-satisfiability cannot be solved in subexponential time in the number of variables. It strengthens the practical implications of NP-completeness with finer limits on exact algorithms.
Polynomial-time reduction: A transformation between problems, computable in polynomial time, that preserves yes-or-no answers. These reductions formalize the claim that every NP problem is no harder than a given one.
Boolean satisfiability problem: The decision problem of whether a Boolean formula has an assignment that makes it true. Its NP-completeness is the starting point for many hardness proofs.

Linked from 22 pages