In
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 ...
, the complement 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 ...
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
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 ...
of this set over some fixed domain is its complement problem.
For example, one important problem is whether a number is a
prime number
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
. Its complement is to determine whether a number is a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
(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
In computability theory, a Turing reduction from a decision problem A to a decision problem B is an oracle machine which decides problem A given an oracle for B (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to s ...
from every problem to its complement problem. The complement operation is an
involution
Involution may refer to:
* Involute, a construction in the differential geometry of curves
* '' Agricultural Involution: The Processes of Ecological Change in Indonesia'', a 1963 study of intensification of production through increased labour inpu ...
, meaning it "undoes itself", or the complement of the complement is the original problem.
One can generalize this to the complement of 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 ...
, 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
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the instan ...
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.
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.
Similarly, probabilistic classes such as
BPP
BPP may refer to:
Education
* BPP Holdings, a holding company based in the United Kingdom
* BPP Law School, a law school based in the United Kingdom and a constituent school of BPP University
* BPP University, a private university based in the ...
,
ZPP,
BQP or
PP which are defined symmetrically with regards to their ''yes'' and ''no'' instances are closed under complement. In contrast, classes such as
RP and co-RP define their probabilities with one-sided error, and so are not (currently known to be) closed under complement.
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.
References
{{reflist
Computational complexity theory