NP-hard

The complexity theory, a branch of theoretical computer science, deals with the classification of problems. An important class of problems is the complexity class NP, the class of all decision problems that can be checked efficiently for a solution found. Here, NP stands for Nondeterministic Polynomial - so there is a non-deterministic Turing machine that can solve the problem in polynomial time. NP-hardness and NP- hardness ( mistranslation of the English NP- hard) denotes a characteristic of a problem. An NP- hard problem is at least as " hard " as any problem in NP. This means that an algorithm that solves a NP- hard problem, can be used to solve all the problems in the NP.

Intuition

To compare the severity of problems, problem reductions are used in theoretical computer science. A problem is reduced to a different, when each algorithm that solves the second problem can also be used to solve the first one. For example, the squaring of a number is reducible to the multiplication of two numbers, because every algorithm that can multiply two numbers, can also be a square number ( by multiplying it with itself). Multiply is therefore at least as difficult as squaring in this sense. In the reduction is important that they be efficient. In complexity theory, efficiency is formalized by the requirement that the number of computation steps, which performs the reduction, is bounded by a polynomial in the input length; such a reduction is called Polynomialzeitreduktion.

In the early 1970s showed Stephen A. Cook and Leonid Levin independently that there is in NP problem can be reduced to any other problem in NP in polynomial time: the satisfiability of propositional logic (SAT, satisfiability of English ). The problem SAT is therefore a heaviest problem in NP ( set of Cook). However, it is not the most difficult problem, because Richard M. Karp showed that there are problems in NP can be reduced to the SAT, which therefore are just as hard as SAT. These serious problems in NP are called NP-complete and all the problems that are at least as hard as they are called NP- hard.

Definition

Be a formal language. then is called NP-hard if and only if:

( All of NP are polynomially reducible to. )

This means that is as hard as any problem in NP at least. This intuitive interpretation is justified by the fact that with an algorithm that solves in polynomial time, for every problem from NP could also construct a polynomial algorithm:

But itself can be difficult. In particular, does not necessarily lie in NP ( NP, however additionally in so called NP-complete ).

Example

A classic example of a problem that is NP-hard and is not in NP, is the halting problem for Turing machines. For example, can the satisfiability problem to reduce the halting problem by creating an instance of the satisfiability problem is transformed into a Turing machine which successively trying all the possible allocations and holds whenever a satisfying assignment is found, but otherwise goes into an infinite loop. In addition, the halting problem, but is not even in NP, since it is not decidable.