|
In computational complexity
theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all
decision problems L in NP there is a
polynomial-time many-one
reduction to H. Informally this class can be described as containing the decision problems that are at least as hard
as any problem in NP. This intuition is supported by the fact that if we can find an algorithm A that solves one of these problems H in polynomial time then we can construct a polynomial time algorithm for every problem in NP
by first executing the reduction from this problem to H and then executing the algorithm A.
Assuming language L to be NP-complete,
- 1. L is in NP
- 2. ∀L' in NP, L' ≤ L
NP-Hard assumes language L satisfies property 2, but not necessarily property 1.
The notion of NP-hardness plays an important role in the discusson about the relationship between the
complexity classes P and NP. It is also often
used to define the complexity class NP-complete which is the intersection of
NP and NP-hard. Consequently the class NP-hard can be understood as the class of problems that
are NP-complete or harder.
A common mistake is to think that the "NP" in "NP-hard" stands for "non-polynomial". Although it is widely suspected that
there are no polynomial-time algorithms for these problems, this has never been proved.
Examples
An example of an NP-hard problem is the decision problem SUBSET-SUM which is this: given a set of integers, do any non empty subset of them add up to zero? That
is a yes/no question, and happens to be NP-complete.
There are also decision problems that are NP-hard but not NP-complete, for example the halting problem. This is the problem "given a program and its input, will it run forever?" That's a
yes/no question, so this is a decision problem. It is easy to prove that the halting problem is NP-hard but not
NP-complete. For example the boolean
satisfiability problem can be reduced to the halting problem by transforming it to the description of a Turing machine that tries all truth value assignments and when it finds one
that satisfies the formula it halts and otherwise it goes into an infinite loop. It is also easy to see that the halting problem
is not in NP since all problems in NP are decidable and the halting problem is not.
Alternative Definitions
An alternative definition of NP-hard that is often used replaces polynomial-time many-one reductions with polynomial-time Turing reductions. This
notion of NP-hardness can be formulated for function problems and
not just decision problems.
In this sense, the problem H is NP-hard if and only if every
decision problem L in NP can be solved in polynomial time by an
oracle machine with an oracle for H. (Informally we can think of such a
machine as an algorithm that can call a subroutine for solving H and solves L in polynomial time if the subroutine call takes
only one step to compute.) If we find a polynomial-time algorithm for an NP-hard problem then we have a polynomial-time algorithm
for all problems in NP-easy and indeed for all problems in NP.
Whether this definition of NP-hardness is equivalent with the one at the beginning of this article is still an open problem
and is discussed in more detail in the article on NP-completeness.
|