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.
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 ?
However, the problem of the maximal clique is an NP-hard problem, and many graphs have no clique.
They expand computing into areas where digital logic is not very effective, such as solving combinatorial Np-hard problems with quantum, digital computers are not so good at that.
Now we will reduce the independent set problem to MISP in order to show that MISP is NP-hard.
Within the relevant literature on taking the total weighted completion times into consideration, it has been shown as an NP-hard by Sung and Yoon [5].
Most optimization problems that are well known in computer science are horribly difficult to solve, and this is known as NP-hard. These NP-hard problems show up all over the place, almost always if you have an optimization problem it is NP-hard and it is incredibly difficult to prove that you've found the best answer, arrived at a global optimum."
Therefore, NP-hard problems can be solved efficiently.
Then we prove that the sensing task assignment is NP-hard. Therefore, we design an optimal algorithm based on particle swarm optimization (PSO) to solve the problem.
This motivates the research on linear time algorithms in special classes of graphs for our problem which is an NP-hard variant of MAX CUT.