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'sproblem.

See also computational complexity, halting problem,

Co-NP, NP-hard.

.

[Other examples?]

(1995-04-10)