1. NP-complete 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 Hamiltons 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?]
np-complete |
