NP-complete
<complexity> (NPC, Nondeterministic Polynomial time complete) A set or
property of computational decision problems which is a subset of NP (i.e. can be
solved by a nondeterministic Turing Machine in polynomial time), with the
additional property that it is also NP-hard. Thus a solution for one NP-complete
problem would solve all problems in NP. Many (but not all) naturally arising
problems in class NP are in fact NP-complete.
There is always a polynomial-time algorithm for transforming an instance of any
NP-complete problem into an instance of any other NP-complete problem. So if you
could solve one you could solve any other by transforming it to the solved one.
The first problem ever shown to be NP-complete was the satisfiability 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/.
[Other examples?]
(1995-04-10)
Nearby terms:
NP « np « NPC « NP-complete » NP-hard » NPL » NPPL
