Complement (complexity)
Encyclopedia
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.
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.
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.
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.
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 class 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 reduction
s, many important classes, especially NP
, are believed to be distinct from their complement classes (although this has not been proven).
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.
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 (see Immerman-Szelepcsényi theorem
). The latter has become less surprising now that we know SL equals L
, which is a deterministic class.
Every class which is low
for itself is closed under complement.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complement of a decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is 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
Complement (set theory)
In set theory, a complement of a set A refers to things not in , A. The relative complement of A with respect to a set B, is the set of elements in B but not in A...
of this set over some fixed domain is its complement problem.
For example, one important problem is whether a number is a prime number
Prime number
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
. Its complement is to determine whether a number is a composite number
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
(a number which is not prime). Here the domain of the complement is the set of all integers exceeding one.
There is a Turing reduction
Turing reduction
In computability theory, a Turing reduction from a problem A to a problem B, named after Alan Turing, is a reduction which solves A, assuming B is already known . It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B...
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.
We can generalize this to the complement of a complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
, 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.
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 class 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 reduction
Many-one reduction
In computability theory and computational complexity theory, a many-one reduction is a reduction which converts instances of one decision problem into instances of a second decision problem. Reductions are thus used to measure the relative computational difficulty of two problems.Many-one...
s, many important classes, especially NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, are believed to be distinct from their complement classes (although this has not been proven).
The closure
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
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
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
, which is in the intersection of NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
and co-NP.
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
NL (complexity)
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....
and SL
SL (complexity)
In computational complexity theory, SL 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...
are in fact closed under complement, whereas before it was widely believed they were not (see Immerman-Szelepcsényi theorem
Immerman-Szelepcsényi theorem
In computational complexity theory, the Immerman–Szelepcsényi theorem was proven independently by Neil Immerman and Róbert Szelepcsényi in 1987, for which they shared the 1995 Gödel Prize. In its general form the theorem states that NSPACE = co-NSPACE for any function s ≥ log n...
). The latter has become less surprising now that we know SL equals L
L (complexity)
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...
, which is a deterministic class.
Every class which is low
Low (complexity)
In computational complexity theory, a complexity class B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve...
for itself is closed under complement.