computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...

, co-NP is a

complexity class In computational complexity theory, a complexity class is a set (mathematics), set of computational problems "of related resource-based computational complexity, complexity". The two most commonly analyzed resources are time complexity, time and s ...

. 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 on a set of input values. An example of a decision problem is deciding whether a given natura ...

X is a member of co-NP if and only if its complement is in the complexity class NP. The class can be defined as follows: a decision problem is in co-NP if and only if for every ''no''-instance we 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 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 , the Turing machine ''M'' accepts the pair .

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, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

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) asks whether there exists an Interpretation (logic), interpretation that Satisf ...

: 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 (whatever form it might take) would be equally as complex as for the ''no''-instance of the original NP satisfiability problem.

co-NP-completeness

A problem ''L'' is

co-NP-complete In 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-complete problem with only polynomial ...

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 The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...

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. Because P is closed under complementation, and NP and co-NP are complementary, it cannot be strict in one case and not strict in the other: if P equals NP, it must also equal co-NP, and vice versa. NP and co-NP are also thought to be unequal, and their equality would imply the collapse of the

polynomial hierarchy In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. ...

PH to NP. If they are unequal, 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., . 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., . Thus . The proof that no co-NP-complete problem can be in NP if is symmetrical. co-NP is a subset of PH, which itself is a subset of

PSPACE In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. Formal definition If we denote by SPACE(''f''(''n'')), the set of all problems that can ...

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 mathematics, integer factorization is the decomposition of a positive integer into a product of integers. Every positive integer greater than 1 is either the product of two or more integer factors greater than 1, in which case it is a comp ...

: 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 scientist ...

. 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. See Section 2.2.4 Factoring and Graph Isomorphism, pp. 19–20 of book (pp. 17–18 of linked version).

References

External links

* {{DEFAULTSORT:Co-Np Complexity classes