np-complete

Computing Dictionary

NP-complete definition

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)
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: np-
Next Definition: np-hard
Words Near: np-complete
More from Thesaurus.com
Synonyms and Antonyms for np-complete
More from Reference.com
Search for articles containing np-complete
More from Dictionary.com Translator
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Nearby Words
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature