NP-Complete

From Algorithmist

Jump to: navigation, search
This is a stub or unfinished. Contribute by editing me.

NP-Complete is a class of problems that are the hardest of those in NP.

A problem is considered to be NP-complete if:

  1. It is in NP.
  2. All other problems in NP are reducible to it. (The problem is NP-hard.)

Examples of NP-complete problems are the Traveling Salesperson Problem, Vertex Cover, and 3-SAT.

Retrieved from "http://www.algorithmist.com/index.php/NP-Complete"
Personal tools