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