You are here: irt.org | FOLDOC | 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)
Nearby terms: NP « np « NPC « NP-complete » NP-hard » NP-hilarious » NPL
FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL