computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by ...

, co-NP is a

complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms of ...

. A

decision problem In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...

X is a member of co-NP if and only if its

complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class ...

is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP precisely if only ''no''-instances have a polynomial-length " certificate" and there is a polynomial-time algorithm that can be used to verify any purported certificate. That is, co-NP is the set of decision problems where there exists a polynomial ''p(n)'' and a polynomial-time bounded

Turing machine A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...

''M'' such that for every instance ''x'', ''x'' is a ''no''-instance if and only if: for some possible certificate ''c'' of length bounded by ''p(n)'', the Turing machine ''M'' accepts the pair (''x'', ''c'').

Complementary Problems

While an NP problem asks whether a given instance is a ''yes''-instance, its ''complement'' asks whether an instance is a ''no''-instance, which means the complement is in co-NP. Any ''yes''-instance for the original NP problem becomes a ''no''-instance for its complement, and vice versa.

Unsatisfiability

An example of an

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

problem is the

Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

: given a Boolean formula, is it ''satisfiable'' (is there a possible input for which the formula outputs true)? The complementary problem asks: "given a Boolean formula, is it ''unsatisfiable'' (do all possible inputs to the formula output false)?". Since this is the ''complement'' of the satisfiability problem, a certificate for a ''no''-instance is the same as for a ''yes''-instance from the original NP problem: a set of Boolean variable assignments which make the formula true. On the other hand, a certificate of a ''yes''-instance for the complementary problem would be equally as complex as the ''no''-instance of the original NP satisfiability problem.

Dual Problems

co-NP-completeness

A problem ''L'' is

co-NP-complete In Computational complexity theory, complexity theory, computational problems that are co-NP-complete are those that are the hardest problems in co-NP, in the sense that any problem in co-NP can be reformulated as a special case of any co-NP-comple ...

if and only if ''L'' is in co-NP and for any problem in co-NP, there exists a

polynomial-time reduction In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...

from that problem to ''L''.

Tautology Reduction

Determining if a formula in

propositional logic Propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. It deals with propositions (which can be true or false) and relations b ...

is a tautology is co-NP-complete: that is, if the formula evaluates to true under every possible assignment to its variables.

Relationship to other classes

P, the class of polynomial time solvable problems, is a subset of both NP and co-NP. P is thought to be a strict subset in both cases (and demonstrably cannot be strict in one case and not strict in the other). NP and co-NP are also thought to be unequal. If so, then no NP-complete problem can be in co-NP and no

problem can be in NP. This can be shown as follows. Suppose for the sake of contradiction there exists an NP-complete problem that is in co-NP. Since all problems in NP can be reduced to , it follows that for every problem in NP, we can construct a

non-deterministic Turing machine In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is ''not'' comp ...

that decides its complement in polynomial time; i.e., NP ⊆ co-NP. From this, it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP; i.e., co-NP ⊆ NP. Thus co-NP = NP. The proof that no co-NP-complete problem can be in NP if NP ≠ co-NP is symmetrical.

Integer Factorization

An example of a problem that is known to belong to both NP and co-NP (but not known to be in P) is

integer factorization In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers. If these factors are further restricted to prime numbers, the process is called prime factorization. When the numbers are suf ...

: given positive integers ''m'' and ''n'', determine if ''m'' has a factor less than ''n'' and greater than one. Membership in NP is clear; if ''m'' does have such a factor, then the factor itself is a certificate. Membership in co-NP is also straightforward: one can just list the prime factors of ''m'', all greater or equal to ''n'', which the verifier can confirm to be valid by multiplication and the

AKS primality test The AKS primality test (also known as Agrawal–Kayal–Saxena primality test and cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at ...

. It is presently not known whether there is a polynomial-time algorithm for factorization, equivalently that integer factorization is in P, and hence this example is interesting as one of the most natural problems known to be in NP and co-NP but not known to be in P.

References

External links

* {{DEFAULTSORT:Co-Np Complexity classes