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 ?
Objective: Traditional complexity theory focuses on the dichotomy between p and np-hard problems.
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).
Unfortunately, computing these combinatorial objects is NP-hard and hard to approximate with this objective in general.
Next, we will propose algorithms to solve this NP-hard problem.
That's the sort of ivory tower throw down that leads to blood-drenched chalkboards and dueling solutions to NP-hard problems.
Computation of lucky number of planar graphs is NP-hard.
Community detection is often a NP-hard problem and traditional methods for detecting communities in networks can be concluded into two categories: graph partitioning and hierarchical clustering.
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.
It has been demonstrated that this problem is usually NP-hard in the strong sense[2].
As the number of cities grows, it becomes np-hard (Non- deterministic Polynomial time hard) problem.
Gupta [2] and Hoogeveen [3] proved that the two stage hybrid flow shop scheduling problem is NP-hard in the strong sense even if there is only one machine on the first stage and there are two machines on the second stage.
The VRP belongs to the class NP-Hard, because the TSP (Travelling Salesman Problem) belongs to this class, and is a particular case of VRP, when there is only one vehicle available, and there are no capacity constraints and total distance traveled [2].