NP (complexity class)

In computer science , NP (for nondeterministic polynomial time ) denotes a fundamental complexity class from the field of complexity theory .

Described intuitively, NP contains the decision problems for which there is evidence for “yes” answers that can be verified efficiently (in polynomial time ). However, it can sometimes be laborious to find such a proof. An alternative description of NP is the class of all decision problems that can be solved by a nondeterministic Turing machine (NTM) with regard to the input length in polynomial time. An instance is answered with “yes” if at least one of the possible calculations of the nondeterministic Turing machine does this.

Problems that are complete for class NP are particularly interesting . NP -complete problems probably cannot be solved efficiently. All known deterministic algorithms for these problems require exponential computation, and it is strongly believed that there are no more 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 traveling salesman problem .

Sometimes NP is wrongly called the class of problems that cannot be solved in polynomial time. The class NP only defines an upper bound for the complexity of the problems it contains and also contains all problems that can be solved by a deterministic machine in polynomial time. It is true that for NP -complete problems (and some more in NP ) it is not known whether they can be solved deterministically in polynomial time; it is believed that this is not the case.

Equivalent characterizations

According to an alternative definition, a decision problem is in NP if and only if a given solution for the corresponding search problem can be checked by a deterministic Turing machine in polynomial time. In the German-speaking world, this definition has the advantage that the expression NP problem can also be read as a proof-polynomial problem, i.e. the proof of a positive answer can be carried out in a polynomially limited time.

Another characterization of NP is in the descriptive complexity theory . According to Fagin's theorem , a language L is in NP if and only if there is a sentence in the existential predicate logic of the second order (SO∃) that describes L.

Formal definition

A formal definition of both characterizations can be given as follows:

Language acceptance definition

A language is in if there is a nondeterministic Turing machine and a polynomial such that: ${\ displaystyle L}$ ${\ displaystyle {\ text {NP}}}$ ${\ displaystyle M}$ ${\ displaystyle p}$

If you enter stops after a maximum of steps (each run from to has a maximum length ). ${\ displaystyle x}$ ${\ displaystyle M}$ ${\ displaystyle p (| x |)}$ ${\ displaystyle M}$ ${\ displaystyle x}$ ${\ displaystyle p (| x |)}$
${\ displaystyle x \ in L}$ if and only if there is at least one accepting run from up . ${\ displaystyle M}$ ${\ displaystyle x}$

In other words, if and only if there is a polynomial computational time constrained verifier for all words from with . ${\ displaystyle L \ in {\ text {NP}}}$ ${\ displaystyle M}$ ${\ displaystyle L}$ ${\ displaystyle L (M) = L}$

Search problem definition

A language L is in NP if there is a relation and a polynomial p such that: ${\ displaystyle R_ {L} \ subseteq \ {0.1 \} ^ {*} \ times \ {0.1 \} ^ {*}}$

${\ displaystyle R_ {L}}$ is recognized by a deterministic and polynomial time constrained Turing machine, and
x ∈ L if and only if there is y with | y | ≤ p (| x |) and . ${\ displaystyle (x, y) \ in R_ {L}}$

Here, y and certificate of x called, and, in truth the case, a "proof" ( proof ) or a "witness" ( witness ) for x , hence the (Engl.) Name "witness relation" of the relationship . ${\ displaystyle R_ {L}}$

Equivalence of Definitions

If there is an NTM M that recognizes L , then for every x ∈ L there is an accepting calculation of M , which can be encoded in a string . The relation is then for all x ∈ L and fulfills the above properties, because the accepting calculation is polynomially restricted in the length of x and can be checked deterministically in polynomial time. ${\ displaystyle \ alpha _ {M} (x)}$ ${\ displaystyle R_ {L}}$ ${\ displaystyle R_ {L} = (x, \ alpha _ {M} (x))}$

There is, conversely, a relation as defined above, so a can NTM M be constructed that a corresponding y advises first non-deterministic, and then by means of a DTM for checking whether , so x ∈ L . ${\ displaystyle R_ {L}}$ ${\ displaystyle R_ {L}}$ ${\ displaystyle (x, y) \ in R_ {L}}$

Relationship to other complexity classes

The class of decision problems whose complements lie in NP is denoted by Co-NP . NP and Co-NP are not disjoint because of . It is unclear whether NP = Co-NP holds. However, this would follow from P = NP , since P is closed with a complement. ${\ displaystyle P \ subseteq {\ mbox {NP}} \ cap {\ mbox {Co-NP}}}$

Usually only inclusion relations are known for relationships between complexity classes . It is not known whether there is a true subset relationship in each case:

L ⊆ NL ⊆ LOGCFL ⊆ NC ⊆ P ⊆ NP ⊆ PSPACE = NPSPACE ⊆ EXPTIME ⊆ NEXPTIME

The following true inclusions are known:

LOGCFL ⊂ PSPACE

P ⊂ EXPTIME

Q ⊂ NP

Properties of NP

The class NP is completed under

Union
average
Concatenation
Kleene star
epsilon-free homomorphisms
inverse homomorphisms

Open issues

The answers to the following questions are not yet known:

NP ⊆ P ? ( P-NP problem )
PSPACE ⊆ NP ?
EXPTIME ⊆ NP ?
NP ⊆ Co-NP ?
Co-NP ⊆ NP ?

Known issues in NP

Karps 21 NP-complete problems
SAT is NP -complete.
The clique problem is NP -complete.
The Hamilton cycle problem is NP -complete.
The backpack problem is NP -complete.
Independent set is NP -complete.
CSAT is NP -complete.
3-SAT is NP -complete.
NODE-COVER is NP -complete.
Salesman problem is NP -complete.

All problems in P are also contained in NP , since an equivalent nondeterministic Turing machine can be constructed from every deterministic Turing machine. To decide the issue of whether two graphs are isomorphic ( Graphisomorphieproblem ) is also in NP and it is not known whether it NP is -complete.

Web links

NP . In: Complexity Zoo. (English)

swell

Christos H. Papadimitriou: Computational Complexity . Addison-Wesley, ISBN 978-0201530827

Individual evidence

↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 461 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 457 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 449 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 453 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 460 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).
↑ John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 469 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[1] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 461 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[2] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 457 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[3] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 449 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[4] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 453 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[5] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 460 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).

[6] John E. Hopcroft , Rajeev Motwani , Jeffrey Ullman : Introduction to Automata Theory, Formal Languages, and Complexity Theory . 2., revised. Edition. Pearson Studium, Munich 2002, ISBN 3-8273-7020-5 , p. 469 (Original title: Introduction to automata theory, languages, and computation . Translated by Sigrid Richter, Ingrid Tokar).