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.

EditText of this page (last edited December 10, 2012) or FindPage with title or text search