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)