Added to Favorites

Computing Dictionary

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)

Explore Dictionary.com

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

Translate NP-hard into French

Translate NP-hard into German

Translate NP-hard into Italian

Translate NP-hard into another language

Dictionary.com Word FAQs

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

Matching Quote

Nearby Words

Copyright © 2014 Dictionary.com, LLC. All rights reserved.