NP-hard

(redirected from NP-Hard Problem)

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 order to solve the problem, they developed two meta- heuristic algorithms, namely, simulated annealing algorithm and variable neighborhood search for this NP-hard problem.
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.
Since it is an NP-hard problem, it is not easy to get a polynomial time algorithm.
The Max-Sat problem is obviously a problem of optimization; it has been classified as a NP-hard problem [1].
It may not be possible to polynomially transform a solution to an NP-complete problem into a solution to an NP-hard problem.
Any NP-hard problem can be shown to be NP-complete for at least some instances, but not necessarily for all instances; the problem becomes `hard' because almost every instance is difficult to compute.
Problem 1 is a NP-Hard problem (Scholl and Christian 2006).
The FLP is NP-hard problem, so it is hard to solve even small-size problem using mathematical model.
However in most cases one is faced with NP-hard problems and therefore in practice one has been often satisfied with only a local optimum obtained with some ad-hoc (local) optimization algorithm.
Exact Algorithms for NP-Hard Problems, Lecture Notes in Computer Science, 2003, v.