NP completeness

Set diagram of the possible relationships between P , NP and the sets of NP-hard and NP-complete problems.

In computer science , a problem is called NP-complete ( complete for the class of problems that can be solved nondeterministically in polynomial time) if it is one of the most difficult problems in the class NP , i.e. is both in NP and NP-difficult is. Colloquially, this means that it can probably not be solved efficiently.

Formally, NP-completeness is only defined for decision problems (possible solutions only “yes” or “no”), while for other problem types one speaks of NP-equivalence ( e.g. for search problems or optimization problems ). Colloquially, however, this distinction is often not made, so that one speaks in general of "NP-complete problems", regardless of whether a decision problem is present or not. This is possible because different problem types can be converted into one another (reducible to one another).

A decision problem is NP-complete if it is

• is in the complexity class NP : A deterministically operating computer only needs a lot of polynomial time to decide whether a proposed solution to an associated search problem is actually a solution, and
• One of the NP-hard problems is: All other problems, the solutions of which can be checked deterministically in polynomial time, can be traced back to the problem in such a way that this tracing on a deterministic computer takes at most polynomial time. One speaks of a polynomial time reduction .

The class of all NP-complete problems is denoted by NP-C (complete). The properties of these and other classes are explored in complexity theory , a branch of theoretical computer science .

An essential property of NP-complete problems is that they can probably not be solved efficiently , so that their solution on real computers takes a lot of time. In practice, this property does not always have a negative effect, that is, for many NP-complete problems there are solution methods with which they can be solved within an acceptable time for orders of magnitude that occur in practice.

Many important problems that arise in practice are NP-complete, which makes NP-completeness a central concept in computer science. This importance is reinforced by the so-called P-NP problem :

1. For no NP-complete problem could it be shown that it could be solved in polynomial time.
2. If only one of these problems were solvable in polynomial time, then every problem in NP would be solvable in polynomial time, which could (but does not necessarily have to be) of great practical importance.

Since Cook introduced NP-completeness, completeness has been expanded into a general concept for any complexity class.

history

The concept of NP-completeness was introduced in 1971 by Stephen A. Cook in what is now what is known as the Cook Theorem . In it he showed that SAT is NP-complete and thus a problem exists which satisfies the definition of NP-completeness. Today there is much simpler constructive evidence for the existence of such problems, but the languages used for them are very artificial. Cook's merit is also to have provided this evidence for a particularly interesting language.

Building on the work of Cook, Richard Karp was able to present another groundbreaking paper in 1972 that made the theory of NP-completeness even more popular. Karp's merit is to have consistently used the technique of polynomial time reduction to prove the NP-completeness for a further 21 popular problems .

definition

A problem (more precisely: a decision problem ) L is called NP-complete if and only if:

• L is in the class NP , that is, and ${\displaystyle L\in {\rm {NP}}}$
• L is NP-hard , that is . ${\displaystyle \forall L'\in {\rm {NP}}:L'\preceq _{p}L}$

The latter condition means that every problem in NP can be reduced to L by a polynomial time reduction .

Proof of NP completeness

The proof of the first property for a given problem is usually easy. One “guesses” a solution and shows that one can verify in polynomial time whether the solution really applies. In guessing the (correct) solution, nondeterminism is found again.

The proof of the second property, which is called NP-hard by itself (or through incorrect back-translation from English 'NP-hard' with NP-hard ), is more difficult. In particular, it causes problems to show a statement for any problem in NP . Hence, one usually takes a similar problem, for which NP-completeness is already known, and reduces it to the problem for which the property of NP-severity is to be shown. From the transitivity of polynomial time reductions it follows that all other problems from NP can also be reduced to the problem under consideration.

Strictly speaking, the above definition requires a proof of existence. It is not immediately apparent that such problems even exist. However, it is easy to construct such a problem. However, a problem constructed in this way is hardly relevant in practice. Cook was able to show, however, that the satisfiability problem of propositional logic is NP-complete , and has thus provided evidence for a problem relevant in practice. In contrast to other problems, this proof could of course not yet be carried out via the transitivity of polynomial time reductions as shown above and had to be done directly.

NP equivalence

NP-completeness is only defined for decision problems, i.e. for problems that can be traced back to the word problem of a formal language, for which the answer is either yes or no . For optimization problems and search problems there is the designation of NP equivalence .

Approximation

Problems that lie in NP can be further subdivided in terms of their complexity, depending on how well they can be solved approximately . The graph coloring problem, for example, can only be approximated very poorly, while other problems can be approximated as well as desired using so-called approximation schemes.

Strong NP-completeness

An NP-complete problem is called strongly NP-complete if it is also NP-complete if it is restricted to such input instances that only contain numbers (as numerical parameters) whose size is polynomially restricted in relation to the input length ( such a problem is always in NP). In other words: If you modify the problem in such a way that all numerical parameters in the unary system are in the input, it remains NP-complete. For strongly NP-complete problems there are no pseudopolynomial algorithms under the assumption NP not equal to P. These are algorithms whose runtime is polynomial if the size of all numbers occurring in the input is polynomially limited in the input length.

An example of a problem for which a pseudopolynomial algorithm exists is the backpack problem . With algorithms that are based on the principle of dynamic programming , a running time that is limited can be achieved. The computing time is thus polynomial if the number (the limit for the maximum permitted utility value) is only polynomial in relation to the input length . Such NP-complete problems, with a pseudopolynomial algorithm, are also called weakly NP-complete . ${\displaystyle {\mathcal {O}}(n^{2}\cdot V)}$ ${\displaystyle V}$ ${\displaystyle n}$

swell

1. ↑ See page 157 in the book "Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics" by Juraj Hromkovič, published by Springer Verlag, 2001, ISBN 3519004445 , ISBN 9783540668602 .
2. ^ Leslie Hall: Computational Complexity. Retrieved December 10, 2012 . 

literature

• Michael R. Garey and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness . Freeman, San Francisco 1978, ISBN 0716710455
• Stephen A. Cook: The Complexity of Theorem Proving Procedures . In Annual ACM Symposium on Theory of Computing (STOC) , pp 151--158, 1971.

Web links

• NPC (NP-Complete) . In: Complexity Zoo. (English)
• Compendium of NP optimization problems (English)
• Complexity results for scheduling problem (English)