NP-Complete

From Algorithmist
Jump to navigation Jump to 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.