Computing Dictionary
NP-complete definition
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)
