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

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)
References in periodicals archive ?
As [P.sub.11] is an NP-hard problem, we can use an artificial intelligence algorithm to obtain the optimal CC and RB allocation scheme.
(2013) showed that a multi-objective optimization problem is a non-deterministic polynomial NP-hard problem. In Wang, Lai, and Shi's study (2011), Pareto optimal solutions are defined as the non-dominated solution for Multi-Objective Optimization (MOO) problem.
The PSO algorithm is good at NP-hard problem optimization [22].
VRP is an NP-hard problem, and a heuristic algorithm is usually needed to solve this kind of problem.
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).
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.
In this section, we prove that the problem [V.sub.m] [right arrow] batch [absolute value of [p.sub.j]= p,[w.sub.j]][summation][C.sub.j] + X(x) is ordinarily NP-hard by a reduction of the Partition Problem [13] which is a known NP-hard problem and provides a dynamic programming algorithmin pseudopolynomial time.
It is an NP-hard problem such that exhaustive algorithms cannot be applied.
Reference [14] shows that solving the aforementioned coverage problem with MINLP is NP-hard problem.