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.