<*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?]

Last updated: 1995-04-10

Try this search on Wikipedia, OneLook, Google

**Nearby terms:**
NP « np « NPC « **NP-complete** » NP-hard » NPL » NPPL

Loading

Copyright Denis Howe 1985