Printer Friendly
Dictionary, Encyclopedia and Thesaurus - The Free Dictionary
3,921,355,701 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-hard
(redirected from NP-Hard Problem)

    Also found in: Wikipedia 0.01 sec.
NP-hard [¦en¦pē ′härd]
(computer science)
Referring to problems at least as hard as or harder than any problem in NP. Given a method for solving an NP-hard problem, any problem in NP can be solved with only polynomially more work.
(complexity)NP-hard - A set or property of computational search problems. A problem is NP-hard if solving it in polynomial time would make it possible to solve all problems in class NP in polynomial time.

Some NP-hard problems are also in NP (these are called "NP-complete"), some are not. If you could reduce an NP problem to an NP-hard problem and then solve it in polynomial time, you could solve all NP problems.

See also computational complexity.
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
 
Any NP-hard problem can be shown to be NP-complete for at least some instances, but not necessarily for all instances; the problem becomes `hard' because almost every instance is difficult to compute.
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.