Computing (FOLDOC) dictionary
Jump to user comments
complexity (NPC, Nondeterministic Polynomial time complete)
is a subset of NP
(i.e. can be solved by a
with the additional property that it is also NP-hard
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.
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