NP-hard

(redirected from NP hard)

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.

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.

References in periodicals archive ?
In recent years, the genetic algorithms for solving NP hard problems have achieved great results [1] [2] [3] [4].
The 0/1 Knapsack Problem is a well-known NP hard problem [8] [9] [10] [11] as it appears in many real life world with different application.