np-hard

Computing Dictionary

NP-hard definition

complexity
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.
[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-complete
Next Definition: npa
Words Near: NP-hard
More from Thesaurus.com
Synonyms and Antonyms for NP-hard
More from Reference.com
Search for articles containing NP-hard
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