Co-NP

In complexity theory , Co-NP denotes a complexity class . It contains exactly those languages ​​whose complement is in class NP . The class Co-NP therefore consists of the languages ​​for which a proof that a word does not belong to the language can be checked in polynomial time by a deterministic Turing machine .

Formal definitions

The class Co-NP is defined as , where denotes the complement of the language L. ${\displaystyle \{L\mid {\bar {L}}\in \mathbf {NP} \}}$ ${\displaystyle {\bar {L}}}$

Analogous to NP there is an alternative definition for Co-NP via verifying deterministic Turing machines . Accordingly, a language L is in Co-NP if and only if there is a deterministic Turing machine M for which it holds that

• ${\displaystyle x\not \in L\iff \exists y\colon M(x,y)=1}$,
• the running time of M (x, y) is polynomially bounded in x .

Equivalently, one can demand that for the first point . ${\displaystyle x\in L\iff \forall y\colon M(x,y)=0}$

A third equivalent definition uses a calculation model based on that of the nondeterministic Turing machine . Accordingly, a language L is in Co-NP if and only if there is a nondeterministic Turing machine N and a polynomial p for which:

• When entering x, N always stops after a maximum of steps. ${\displaystyle p(|x|)}$
• N accepts an input if and only if all possible runs of N accept input x . ${\displaystyle x\in L}$

Co-NP completeness

Analogous to other complexity classes, one can define complete problems within Co-NP . A language is called L Co-NP -complete if and only if the following two conditions are met:

1. The language L is itself from Co-NP .
2. For each language L ' from Co-NP the following applies :, where describes the polynomial time reduction . ${\displaystyle L'\leq _{p}L}$ ${\displaystyle \leq _{p}}$

If only the second property is fulfilled, one speaks of Co-NP difficult languages.

An example of a Co-NP full language is TAUTOLOGY. TAUTOLOGY contains all Boolean formulas that are tautologies , that is, they will be evaluated with every variable assignment with true. TAUTOLOGY can be reduced to the complement of SAT , since a formula cannot be fulfilled if and only if its negation is a tautology. The complement of SAT is an example of Co-NP full language, which can be inferred from Cook and Levin's theorem . Accordingly, TAUTOLOGIE Co-NP is also complete. In general, for all NP -complete languages, their complement is Co-NP -complete.

A deterministic polynomial time algorithm for a Co-NP -complete problem would show that P = Co-NP and therefore the class Co-NP would be closed with a complement. This would solve the P-NP problem , since in this case P = NP = Co-NP would apply.

Relationship to other complexity classes

The complexity class P is a subset of Co-NP . The class Co-NP is in turn contained in the complexity class PSPACE . It is not known whether both subsets are true subsets .

The cut of NP and Co-NP contains class P , but it is unknown whether there are other languages ​​in this cut.

Relationship of Co-NP and NP

It is not yet known how NP and Co-NP are related to each other, but it is assumed that NP ≠ Co-NP . The class Co-NP is a class in the polynomial time hierarchy in which it is denoted by. If NP = Co-NP , the polynomial time hierarchy would collapse up to the 1st level, which would mean that PH = Co-NP , but in this case it would not be possible to say anything about whether P = NP . On the other hand, if P = NP , then the polynomial time hierarchy collapses at the lowest level, and NP = Co-NP would follow. It is not known whether P ≠ NP also implies NP ≠ Co-NP . ${\displaystyle \Pi _{p}^{1}}$

If A is a NP -complete language is, then when exactly then NP = co-NP . The non-trivial part of the equivalence can be shown as follows: ${\displaystyle A\in \mathbf {Co{\text{-}}NP} }$

${\displaystyle \subseteq }$: Be . Because NP is heavy , is , and with it . Because is , and thus is , so . ${\displaystyle L\in \mathbf {NP} }$ ${\displaystyle A}$ ${\displaystyle L\leq _{p}A}$ ${\displaystyle {\bar {L}}\leq _{p}{\bar {A}}}$ ${\displaystyle A\in \mathbf {Co{\text{-}}NP} }$ ${\displaystyle {\bar {A}}\in \mathbf {NP} }$ ${\displaystyle {\bar {L}}\in \mathbf {NP} }$ ${\displaystyle L\in \mathbf {Co{\text{-}}NP} }$

${\displaystyle \supseteq }$: . ${\displaystyle L\in \mathbf {Co{\text{-}}NP} \Rightarrow {\bar {L}}\in \mathbf {NP} \Rightarrow {\bar {L}}\in \mathbf {Co{\text{-}}NP} \Rightarrow L\in \mathbf {NP} }$

The following theorem can be shown analogously: If A Co-NP -complete, then if and only if NP = Co-NP . ${\displaystyle A\in \mathbf {NP} }$

supporting documents

1. ↑ Boaz Barak: NP completeness, CoNP, the Polynomial Hierarchy and P / poly (lecture notes) (pdf; 174 kB) Accessed April 26, 2013.
2. ↑ Sanjeev Arora, Boaz Barak: Computational Complexity . Cambridge University Press ,, ISBN 978-0-521-42426-4 , p. 57.