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.

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 fact, it has been shown that the general problem of solving systems of linear equations with interval coefficients is NP-hard which is extremely difficult to be solved.
Exact Algorithms for NP-Hard Problems, Lecture Notes in Computer Science, 2003, v.
SVP is an NP-hard problem (Khot 2005) and it is the core of the proposed cipherto ensure higher security compared to the existing stream ciphers discussed earlier.
As theory of complexity has certified that scheduling problem is part of the group of NP-hard problems, completely different approach is thus necessary in optimization of scheduling.
The allocation problem of SSCFLP requires a knapsack algorithm which is itself a pseudo-polynomial time algorithm or the NP-hard Generalized Assignment Problem
It is one of the most famous NP-Complete problems, and even approximating the chromatic number within an acceptable ratio is NP-hard [7].
Unfortunately, finding the optimal solution for the graph partitioning problem is known to be NP-hard for all non-trivial cases and the decision formulation is NP-complete [7].
However, in the late 1980s, mathematicians showed that computing the Jones polynomial belongs to the famous family of what they call NP-hard problems.
Saalfeld believes that NP-complete problems, and especially those that are classed NP-hard, are not likely to be solved by more computer power.
The NP-hard class is a superset containing the NP-complete class.