NP severity

Set diagram of the possible relationships between P , NP and the sets of NP-hard and NP-complete problems. It should be noted that on the right-hand side the empty language and its complement are left out (both are in P and NP, but not NP-difficult).

NP severity describes a property of an algorithmic problem .

The complexity theory , a branch of theoretical computer science , deals with the classification of problems with respect to their complexity. An important problem class is the complexity class NP , the class of all decision problems for which a found solution can be efficiently checked. NP stands for nondeterministic polynomial time . An NP-hard problem is at least as "difficult" as all problems in NP. This means that an algorithm that solves an NP-hard problem can be used by means of a reduction to solve all problems in NP.

The colloquial term NP hardness is a mistranslation of the English NP hard .

intuition

In order to compare the severity of problems, problem reductions are used in theoretical computer science. A problem A is said to be reducible to another problem B, if every algorithm that solves B can also be used to solve A by converting a problem instance of A into an instance of B and then solving it.

If one wants to make statements about the efficiency of problems through reductions, the efficiency of the reduction is also important. Here efficiency is formalized by the requirement that the number of calculation steps that the reduction performs is limited by a polynomial in the input length; such a reduction is called a polynomial time reduction . If one problem can be reduced to a second in polynomial time and the second can be solved in polynomial time, one can also solve the first in polynomial time.

In the early 1970s showed Stephen Cook and Leonid Levin independently that there is a problem in NP can be reduced to the all other problems in NP in polynomial time: the satisfiability of propositional logic (SAT from English satisfiability ). The problem SAT is thus a heaviest problem in NP ( Cook's Theorem ). However, it is not the only hardest problem, because Richard M. Karp showed that there are problems in NP to which SAT can be reduced , which are just as difficult as SAT. These hardest problems in NP are called NP-complete . All problems, including those outside of NP, which are at least as difficult as them (to which SAT can be reduced in polynomial time), are called NP-difficult.

definition

Be a formal language. is then called NP-difficult if the following applies: ${\ displaystyle L '\ subseteq \ Sigma ^ {*}}$ ${\ displaystyle L '}$

${\ displaystyle \ forall \, L \ in {\ rm {NP}}: L \ preceq _ {\ rm {p}} L '}$ (All from NP are polynomially reducible to .) ${\ displaystyle L}$ ${\ displaystyle L '}$

This means that it is at least as difficult as any problem from NP. This intuitive interpretation is justified by the fact that with an algorithm that solves in polynomial time , a polynomial algorithm could also be constructed for every problem from NP: ${\ displaystyle L '}$ ${\ displaystyle A}$ ${\ displaystyle L '}$

first perform the reduction to and ${\ displaystyle L '}$
then algorithm . ${\ displaystyle A}$

${\ displaystyle L '}$ however, itself can also be more severe. In particular, it does not necessarily have to be in NP ( but also lies in NP, so it is called NP-complete ). ${\ displaystyle L '}$ ${\ displaystyle L '}$ ${\ displaystyle L '}$

example

A classic example of a problem that is NP-hard and not in NP is the holding problem for Turing machines . For example, the satisfiability problem can be reduced to the holding problem by transforming an instance of the satisfiability problem into a Turing machine, which successively tries all possible assignments and stops as soon as a satisfying assignment is found, but otherwise goes into an endless loop. In addition, the holding problem itself does not lie in NP, since it cannot be decided at all .

literature

Michael R. Garey and David S. Johnson: Computers and Intractability . A Guide to the Theory of NP Completeness. WH Freeman and Company, New York 1979, ISBN 0-7167-1045-5 , Chapter 5: NP-Hardness.