In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. Equivalently, if we define decision problems as sets of finite strings, then the complement of this set over some fixed domain is its complement problem. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ... In set theory and other branches of mathematics, two kinds of complements are defined, the relative complement and the absolute complement. ...

For example, one important problem is whether a number is a prime number. Its complement is to determine whether a number is a composite number (a number which is not prime). Here the domain of the complement is the set of all integers exceeding one. In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are one and itself. ... A composite number is a positive integer that can be factored as a product of two or more prime numbers. ...

There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem. In computational complexity theory, a Turing reduction from a problem A to a problem B is, intuitively, a reduction which easily solves B, assuming A is easy to solve. ... This page is about involution in mathematics; for involution in philosophy and integral theory, see Involution (philosophy). ...

We can generalize this to the complement of a complexity class, called the complement class, which is the set of complements of every problem in the class. If a class is called C, its complement is conventionally labelled co-C. Notice that this is not the complement of the complexity class itself as a set of problems, which would contain a great deal more problems. In computational complexity theory, a complexity class is a set of problems of related complexity. ...

A class is said to be closed under complement if the complement of any problem in the class is still in the class. Because there are Turing reductions from every problem to its complement, any problem which is closed under Turing reductions is closed under complement. Any class which is closed under complement is equal to its complement class. However, under many-one reductions, many important classes, especially NP, are believed to be distinct from their complement classes (although this has not been proven). In computational complexity theory, a many-one reduction is a reduction which converts instances of a decision problem problem A into instances of a decision problem B. We write A ≤m B or A is many-one reducible to B. If we have an algorithm N which solves instances of... In computational complexity theory, NP (Non-deterministic Polynomial time) is the MONKEY ...

The closure of any complexity class under Turing reductions is a superset of that class which is closed under complement. The closure under complement is the smallest such class. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Some interesting problems fall into such intersections, such as the integer factorization, which is in the intersection of NP and co-NP. In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ... In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the MONKEY ... In the complexity theory, co-NP is the complexity class that contains the complements of decision problems in the complexity class NP. The complement of a decision problem is here defined as the problem with the yes and no answers reversed, or if we define decision problems as sets of...

Every deterministic complexity class (DSPACE(f(n)), DTIME(f(n)) for all f(n)) is closed under complement, because one can simply add a last step to the algorithm which reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths which accept and paths which reject, and all the paths reverse their answer, there will still be paths which accept and paths which reject — consequently, the machine accepts in both cases.

Some of the most surprising complexity results shown to date showed that the complexity classes NL and SL are in fact closed under complement, whereas before it was widely believed they were not. The latter has become less surprising now that we know SL equals L, which is a deterministic class. In computational complexity theory, NL is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space. ... In computational complexity theory, SL (Symmetric Logspace) is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ...