(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 nondeterministicTuring 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..[Other examples?](1995-04-10)