# NP-hard

Also found in: Wikipedia.

## 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.

McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

## NP-hard

(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.

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.

This article is provided by FOLDOC - Free Online Dictionary of Computing (

**foldoc.org**)Want to thank TFD for its existence? Tell a friend about us, add a link to this page, or visit the webmaster's page for free fun content.

Link to this page: