NP-hardness

NP-hardness is the property of a problem to which every problem in NP can be reduced in polynomial time under a specified reduction notion. An NP-hard problem need not itself belong to NP or be a decision problem.

Polynomial-time reduction: A transformation computable in polynomial time that maps instances of one problem to instances of another while preserving the relevant answers. NP-hardness is defined by reductions; their precise kind determines which problems qualify.
NP-completeness: The property of a decision problem that is both in NP and NP-hard. It adds membership in NP to the hardness property.
Traveling salesman problem: The optimization problem of finding a shortest tour that visits each city once and returns to its start. Its optimization form is NP-hard, while its decision form is NP-complete.
P: The class of decision problems solvable by a deterministic algorithm in polynomial time. NP-hardness does not itself imply that a problem lies outside P.
NP: The class of decision problems whose yes-instances have certificates verifiable in polynomial time by a deterministic algorithm. Every problem in NP must reduce to an NP-hard problem.
Cook–Levin theorem: The theorem that Boolean satisfiability is NP-complete under polynomial-time many-one reductions. It provides the starting point for many reductions proving NP-hardness.
Knapsack problem: The optimization problem of selecting items to maximize value without exceeding a capacity constraint. Its optimization version is NP-hard, although its decision version is NP-complete.
NP-intermediate problem: A problem in NP that is neither in P nor NP-complete, assuming P differs from NP. Such problems are not NP-hard under standard reductions unless P equals NP.
Polynomial time: A computational resource bound in which running time grows no faster than a polynomial in input length. The defining reductions must be computable within this time bound.
Reduction composition: The process of composing reductions so that hardness transfers from one problem through another. Transitivity lets a known NP-hard problem establish hardness of a new target.

Linked from 12 pages