NP (complexity)

In computer science, NP called ( for non-deterministic polynomial time) a fundamental complexity class in the field of complexity theory.

Described Intuitively, NP contains the decision problems for which there is evidence of " Yes " responses, which can be verified ( in polynomial time ) efficiently. However, it can sometimes be cumbersome to find such a proof. An alternative description of NP as the class of all decision problems that can be solved by a nondeterministic Turing machine with respect to the input length in polynomial time. Here, an instance is answered with " Yes ", if at least one of the possible calculations of the non-deterministic Turing machine does this.

Particularly interesting are problems that are completely to the class NP. NP-complete problems can probably not be solved efficiently. All known deterministic algorithms for these problems require exponential computational complexity, and experienced computer scientists expect that there are no efficient algorithms. The confirmation or refutation of this conjecture is the P- NP problem, one of the most important open problems in computer science. Perhaps the best known NP-complete problem is the problem of the traveling salesman.

Occasionally NP is called the class of non-detachable problems in polynomial time. Here, however, caution is advised: the class NP only defines an upper bound for the complexity of the problems contained and includes all soluble in polynomial time problems. It is true that NP -hard problems probably can not be solved in polynomial time. However, there are NP -hard problems, which does not itself lie in NP, so are even harder than NP.

Equivalent characterizations

According to an alternative definition of a decision problem in NP if and only if a given solution for the corresponding search problem can be verified by a deterministic Turing machine in polynomial time. In German-speaking countries, this definition has the advantage that the term NP problem can be read as a proof - polynomial problem, that is, the detection of a positive response can be accomplished in polynomial time limited.

Further characterization of NP is available in the descriptive complexity theory. By the theorem of Fagin a language L if and only in NP if there is a sentence in the existential predicate second-order logic ( ∃ SO ) indicates that L describes.

Formal definition

Both characterizations can be a formal definition stated as follows:

Acceptance speech definition

A language is in, if there is a nondeterministic Turing machine and a polynomial, so that:

  • If you enter after at most steps holds ( each run of on thus has a maximum length)
  • If and only if there is at least one accepting run of on.

In other words, if and only if there is a polynomial computationally limited verifier for all words of L with.

Search problem definition

A language is in, if there is a relationship and a polynomial, so that:

  • Is recognized by a deterministic polynomial time and bounded Turing machine, and
  • Iff there is with and.

This also is called a certificate of x, and, in truth the case, a "proof" ( proof ) or a "witness" ( witness ) for, hence the (English ) name "witness relation" for the relation.

Equivalence of the definitions

Is there a NTM that recognizes there are at any one accepting account of which can be encoded into a string. The relation is then to all and fulfills the above properties, because the accepting invoice is polynomial in the length of restricted and can be deterministically checked in polynomial time.

If conversely there is a relation according to the above definition, then a NTM can be constructed that initially non-deterministic advises a corresponding, and then checked by means of a DTM for, if so.

Relation to other complexity classes

The class of decision problems whose complements are in NP is denoted by Co -NP. NP and co- NP are not disjoint because. It is unclear whether the following applies. However, this would follow, since is closed under complementation.

Usually only inclusion relations are known for relationships between complexity classes. It is not known whether each of a proper subset relationship applies:

The following real inclusions are known:

Properties of NP

The class NP is closed under

  • Union
  • Average
  • Concatenation
  • Kleene star
  • Epsilon- free homomorphisms
  • Inverse homomorphisms

Open Issues

The answers to these questions are not yet known:

  • ? (P- NP problem )
  • ?
  • ?
  • ?
  • ?

Known Problems in NP

  • Karp's 21 NP- complete problems
  • SAT is NP -complete.
  • The clique problem is NP -complete.
  • The Hamiltonian cycle problem is NP -complete.
  • The knapsack problem is NP -complete.
  • Independent Set is NP -complete.
  • CSAT is NP -complete.
  • 3-SAT is NP -complete.
  • NODE -COVER is NP -complete.
  • Problem of a Salesman is NP -complete.

All problems are also included in, as can construct an equivalent non-deterministic Turing machine from any deterministic Turing machine trivially. The problem to decide whether two graphs are isomorphic to each other ( graph isomorphism ) is also in and it is not known whether it is NP -complete.