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) | ||||
Search Dictionary:
NP-complete definition was found in categories: Language, Idioms & Slang(1) Encyclopedia(1)
NP-complete Definition from Language, Idioms & Slang Dictionaries & Glossaries
| hEnglish - advanced version |
np-complete
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.
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.
NP-complete Definition from Encyclopedia Dictionaries & Glossaries
| Wikipedia English - The Free Encyclopedia |
NP-complete
In complexity theory, the NP-complete problems are the most difficult problems in NP ("non-deterministic polynomial time") in the sense that they are the smallest subclass of NP that could conceivably remain outside of P, the class of deterministic polynomial-time problems. The reason is that a deterministic, polynomial-time solution to any NP-complete problem would also be a solution to every other problem in NP. The complexity class consisting of all NP-complete problems is sometimes referred to as NP-C. A more formal definition is given below.
| See more at Wikipedia.org... |