NP-completeness

In computer science, a problem is said to be NP-complete (complete for the class of problems that can be solved nondeterministically in polynomial time) if it is among the most difficult problems in the class NP, that is, if it is both in NP and NP-hard. This means colloquially that it probably cannot be solved efficiently.

Formally, NP-completeness is defined only for decision problems (possible solutions only "yes" or "no"), while for other types of problems one speaks of NP-equivalence (for example, search problems or optimization problems). Colloquially, however, this distinction is often not carried out, so that one speaks quite generally of "NP-complete problems", regardless of whether a decision problem is present or not. This is possible because different types of problems are convertible (reducible to each other).

A decision problem is NP-complete if it is

  • is in the complexity class NP: A deterministic computer takes only polynomially long time to decide whether a proposed solution to an associated search problem is indeed a solution, and
  • belongs to the NP-hard problems: All other problems whose solutions can be checked deterministically in polynomial time can be reduced to the problem in such a way that this reduction takes at most polynomial time on a deterministic computer. This is called a polynomial time reduction.

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

An essential property of NP-complete problems is that they probably cannot be solved efficiently, i.e. that their solution takes a long time on real computers. In practice, this property does not have a negative effect in every case, i.e., there are solution methods for many NP-complete problems, by means of which they can be solved in acceptable time for orders of magnitude occurring in practice.

Many problems that arise in practice and are important are NP-complete, making NP-completeness a central notion in computer science. This importance is further strengthened by the so-called P-NP problem:

  1. No NP-complete problem has yet been shown to be solvable 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 have (but need not necessarily have) great practical significance.

Since the introduction of NP-completeness by Cook, completeness has been extended to a general concept for arbitrary complexity classes.

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

History

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

Building on Cook's work, Richard Karp was able to present another seminal paper in 1972 that helped the theory of NP-completeness gain even greater popularity. To Karp's credit, he consistently used the technique of polynomial time reduction to prove NP-completeness for another 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 L \in {\rm NP}and
  • L is NP-hard, that is \forall L' \in {\rm NP}: L' \preceq_{p} L.

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


AlegsaOnline.com - 2020 / 2023 - License CC3