NpHard
Last edit December 10, 2012
This is covered more completely in
NpComplete
, but briefly:
A problem is
NpHard
if a solution to it would imply a solution to all NP problems. Problems that are both NP (
NondeterministicPolynomial
) and
NpHard
are said to be
NpComplete
.
Examples of NP-Complete problems include the
TravelingSalesmanProblem
(TSP),
KnapsackProblem
, 3-Satisfiability, and hundreds more.
This falls in an area known as
ComplexityTheory
.