<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 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)