Printer Friendly
Dictionary, Encyclopedia and Thesaurus - The Free Dictionary
3,921,355,771 visitors served.
forum Join the Word of the Day Mailing List For webmasters
?
Dictionary/
thesaurus
Medical
dictionary
Legal
dictionary
Financial
dictionary
Acronyms
 
Idioms
Encyclopedia
Wikipedia
encyclopedia
?

NP-complete

   Also found in: Wikipedia 0.01 sec.
(complexity)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 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/.
Want to thank TFD for its existence? Tell a friend about us, add a link to this page, add the site to iGoogle, or visit the webmaster's page for free fun content.
?Page tools
Printer friendly
Cite / link 		Feedback
Mentioned in?  References in periodicals archive?   Encyclopedia browser?   Full browser?
No references found
 
2] includes NP-complete problems, for which no polynomial time algorithms are known.
Computers for mathematics: theoretical solution versus constructive ... by Khadivi, M.R. / Journal of Computers in Mathematics and Science Teaching
108) The oldest of these is called the class of NP-complete problems.
The computational complexity of automated redistricing: is automation ... by Altman, Micah / Rutgers Computer & Technology Law Journal
 
 
 
Encyclopedia
?

Terms of Use | Privacy policy | Feedback | Advertise with Us | Copyright © 2012 Farlex, Inc.
Disclaimer
All content on this website, including dictionary, thesaurus, literature, geography, and other reference data is for informational purposes only. This information should not be considered complete, up to date, and is not intended to be used in place of a visit, consultation, or advice of a legal, medical, or any other professional.