NP-hard

From Wikipedia, the free encyclopedia

For a gentler introduction, see Complexity classes P and NP.

NP-Hard (Nondeterministic Polynomial-time hard), in computational complexity theory, is a class of problems informally "at least as hard as problems in NP." A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H, i.e. $L \leq_T H$ . In other words, L can be solved in polynomial time by an oracle machine with an oracle for H. Informally we can think of an algorithm that can call such an oracle machine as subroutine for solving H, and solves L in polynomial time if the subroutine call takes only one step to compute. NP-hard problems may be of any type: decision problems, search problems, optimization problems.

As consequences of such definition, we have (note that these are claims, not definitions):

problem H is at least as hard as L, because H can be used to solve L;

since L is NP-complete, and hence the hardest in class NP, also problem H is at least as hard as NP, but H does not have to be in NP and hence does not have to be a decision problem;

since NP-complete problems transform to each other by polynomial-time many-one reduction (also called polynomial transformation), therefore all NP-complete problems can be solved in polynomial time by a reduction to H, thus all problems in NP reduce to H; note however, that this involves combinig two different transformations: from NP-complete decision problems to NP-complete problem L by polynomial transformation, and from L to H by polynomial Turing reduction;

if there is a polynomial algorithm for any NP-hard problem, then there are polynomial algorithms for all problems in NP, and hence $P = N P$ ;

if $P \neq NP$ , then NP-hard problems have no solutions in polynomial time, while $P = N P$ does not resolve whether the NP-hard problems can be solved in polynomial time;

if an optimization problem H has an NP-complete decision version L, then H is NP-hard;

if H is in NP, then H is also NP-complete because in this case the existing polynomial Turing transformation fulfills the requirements of polynomial time transformation;

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

1 Examples
2 Alternative definitions
3 NP-naming convention
4 See also
5 References

[edit] Examples

An example of an NP-hard problem is the decision problem SUBSET-SUM which is this: given a set of integers, does any non empty subset of them add up to zero? That is a yes/no question, and happens to be NP-complete. Another example of an NP-hard problem is the optimization problem of finding the least-cost route through all nodes of a weighted graph. This is commonly known as the Traveling Salesman Problem.

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 in a finite number of operations, while the halting problem, in general, is not.

[edit] Alternative definitions

An alternative definition of NP-hard that is often used restricts NP-Hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction. So, formally, a language L is NP-hard if $\forall L^\prime\in \mathbf{NP}, L^\prime \leq_p L\!$ . If it is also the case that L is in NP, then L is called NP-complete.

[edit] NP-naming convention

The NP-family naming system is confusing: NP-hard problems are not all NP, despite having 'NP' as the prefix of their class name! However the names are now entrenched and unlikely to change. On the other hand, the NP- naming system has some deeper sense, because the NP- family is defined in relation to the class NP: NP-complete - means problems that are 'complete' in NP, i.e. the most difficult to solve in NP; NP-hard - stands for 'at least' as hard as NP (but not necessarily in NP); NP-easy - stands for 'at most' as hard as NP (but not necessarily in NP); NP-equivalent - means equally difficult as NP, (but not necessarily in NP);

[edit] See also

NP-easy

NP-equivalent

Complexity Zoo

[edit] References

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.

Important complexity classes (more)
P • NP • co-NP • NP-C • co-NP-C • NP-hard • UP • #P • #P-C • L • NL • NC • P-C • PSPACE • PSPACE-C • EXPTIME • EXPSPACE • PR • RE • Co-RE • RE-C • Co-RE-C • R • BQP • BPP • RP • ZPP • PCP • IP • PH