|A problem that is at least as hard as the hardest problems in NP.
|A problem that belongs to both NP and is NP-hard.
|Polynomial-time reduction from any NP problem to an NP-hard problem.
|Polynomial-time reduction from any NP problem to an NP-complete problem.
|Membership in NP
|Not necessarily in NP.
|Must be in NP.
|May or may not be solvable in polynomial time.
|Unlikely to have a polynomial-time algorithm; no known polynomial-time algorithm exists.
|Traveling Salesman Problem (TSP), 3-SAT, Vertex Cover.
|Boolean Satisfiability (SAT), Knapsack Problem, Hamiltonian Cycle.
|Serves as a benchmark for the complexity of problems.
|Identifies the hardest problems in NP and serves as a basis for many other complexity results.
|All NP-complete problems are also NP-hard.
|Not all NP-hard problems are NP-complete. Some NP-hard problems may not be in NP.