NP-complete


NP-complete

(complexity)(NPC, Nondeterministic Polynomial time complete)A set or property of computational decision problems whichis a subset of NP (i.e. can be solved by anondeterministic Turing Machine in polynomial time),with the additional property that it is also NP-hard. Thusa solution for one NP-complete problem would solve allproblems in NP. Many (but not all) naturally arising problemsin class NP are in fact NP-complete.

There is always a polynomial-time algorithm for transformingan instance of any NP-complete problem into an instance of anyother NP-complete problem. So if you could solve one youcould solve any other by transforming it to the solved one.

The first problem ever shown to be NP-complete was thesatisfiability problem. Another example is Hamilton's problem.

See also computational complexity, halting problem,Co-NP, NP-hard.

http://fi-www.arc.nasa.gov/fia/projects/bayes-group/group/NP/.