Co-NP

In complexity theory, co- NP denotes a complexity class. In it are exactly the languages ​​contain the complement of which is in the class NP. The class co- NP is thus made up the languages ​​for which a proof that a word is not part of the language, can be deterministically checked in polynomial time by a Turing machine.

Formal definitions

The class co- NP is defined as the complement of the language L is.

Similar to NP there is an alternative definition for co- NP on verifying deterministic Turing machines. Accordingly, a language L in co- NP if and only if there exists a deterministic Turing machine M, which applies to that

• ,
• The running time of M ( x, y) is polynomially bounded in x.

Equivalent of one can for the first point demand that.

A third equivalent definition uses a computational model that on which the non-deterministic Turing machine is ajar. A language L is therefore exactly then in co- NP if there is a nondeterministic Turing machine N and a polynomial p, apply to:

• N halts on input of x is always after at most steps.
• N accepts an input if and only if all possible runs of N on input x accept.

Co- NP- completeness

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

If only the second property is satisfied is called co- NP-hard languages

An example of a co- NP-complete language is TAUTOLOGY. TAUTOLOGY contains all Boolean formulas which are tautologies, ie they will be evaluated each variable assignment with true. TAUTOLOGY can be reduced to the complement of SAT, since a formula is not satisfiable if its negation is a tautology. The complement of SAT is an example of a co- NP-complete language, which can be deduced from the set of Cook and Levin. Thus, even TAUTOLOGY is co- NP -complete. In general, for all NP-complete languages ​​, that its complement is co -NP -complete.

A polynomial time algorithm for a co- NP -complete problem would show that P = co- NP, and thus the class co- NP would be closed under complementation. Thus, the P- NP problem would be solved, since in this case P = NP = co- NP would apply.

Relation 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. From two subset relationships you do not know whether it is a proper subset relationships.

The intersection of NP and co- NP contains the class P, but it is unknown if there are other languages ​​in this section.

Relationship of co- NP and NP

We know not yet how NP and co- NP are to each other, but believed that NP ≠ co- NP. The class of co- NP is a class in the Polynomialzeithierarchie in which it is designated. If NP = co- NP would collapse the Polynomialzeithierarchie to the first stage, which would mean that PH = co- NP, but one was able to say nothing about it in this case, if P = NP. Applies on the other hand, if P = NP, then collapsing the Polynomialzeithierarchie on the bottom step, and it would = co- NP NP follow. It is not known whether, P ≠ NP and NP -NP ≠ Co follows.

If A is an NP-complete language, then if and only if NP = co- NP. Of non-trivial part of the equivalence can be shown as follows:

Analogously, show the following sentence: If A is co- NP-complete, then if and only if NP = co- NP.

Documents

• Complexity class