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 ?
However, this is only true in theory because it is a NP-hard problem to find global optimal partition and exhaustive methods are not useful in practice (Tommikarkkainen, 2006).
First, we formulized the joint optimization problem under a new physical interference model to characterize the sequential detection nature of SIC and proved it to be an NP-hard problem.
The problem as stated is a natural generalization of strongly NP-hard problem P [parallel] [C.
To tackle with such an NP-hard problem, a memetic algorithm (MA) with random path-based direct representation and combinatorial local search methods is developed.
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.
VRP itself is an NP-Hard problem and the researchers' experiences suggested that a Vehicle Routing Problem with Time Windows (VRPTW) was basically a harder problem than VRP [7].
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].
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.