# Complement (complexity)

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Complement_(complexity)
> Markdown URL: https://mediated.wiki/source/Complement_(complexity).md
> Source: https://en.wikipedia.org/wiki/Complement_(complexity)
> Source revision: 1353057319
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [computational complexity theory](/source/Computational_complexity_theory), the **complement** of a [decision problem](/source/Decision_problem) is the decision problem resulting from reversing the *yes* and *no* answers.[1] Equivalently, if we define decision problems as sets of finite [strings](/source/String_(computer_science)), then the [complement](/source/Complement_(set_theory)) of this set over some fixed domain is its complement problem.[2]

For example, one important problem is whether a number is a [prime number](/source/Prime_number). Its complement is to determine whether a number is a [composite number](/source/Composite_number) (a number that is not prime). Here the domain of both the original problem and of the complement is the set of all [natural numbers](/source/Natural_numbers).[3]

There is a [Turing reduction](/source/Turing_reduction) from every problem to its complement problem.[4] The complement operation is an [involution](/source/Involution_(mathematics)), 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](/source/Complexity_class), called the **complement class**, which is the set of complements of every problem in the class.[5] 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 generally 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.[6] Because there are Turing reductions from every problem to its complement, any class that is closed under Turing reductions is closed under complement. Any class that is closed under complement is equal to its complement class. However, under [many-one reductions](/source/Many-one_reduction), many important classes, especially [NP](/source/NP_(complexity)), are believed to be distinct from their complement classes (although this has not been proven).[7]

The [closure](/source/Closure_(mathematics)) of any complexity class under Turing reductions is a superset of that class that 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 that is closed under complement.

Every deterministic complexity class (**[DTIME](/source/DTIME)**(*f*(*n*)), **[DSPACE](/source/DSPACE)**(*f*(*n*)), for any *f*(*n*)) is closed under complement,[8] because one can simply add a last step to the algorithm that reverses the answer. This doesn't work for nondeterministic complexity classes, because if there exist both computation paths that accept and paths that reject a particular instance, and all the paths reverse their answer, there will still be paths that accept and paths that reject — consequently, both the original machine and the modified machine accept the instance.

Similarly, probabilistic classes such as [BPP](/source/BPP_(complexity)), [ZPP](/source/ZPP_(complexity)), [BQP](/source/BQP) or [PP](/source/PP_(complexity)) that are defined symmetrically with regard to their *yes* and *no* instances are closed under complement, whereas classes such as [RP](/source/RP_(complexity)) and **co-RP** that define their probabilities with one-sided error 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](/source/NL_(complexity)) and [SL](/source/SL_(complexity)) *are* in fact closed under complement (see [Immerman–Szelepcsényi theorem](/source/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem)), whereas before it was widely believed they were not. The latter has become less surprising now that we know **SL** equals **[L](/source/L_(complexity))**, which is a deterministic class.

Every class that is [low](/source/Low_(complexity)) for itself is closed under complement.

## References

1. **[^](#cite_ref-1)** [Itô, Kiyosi](/source/Kiyosi_It%C3%B4) (1993), [*Encyclopedic Dictionary of Mathematics, Volume 1*](https://books.google.com/books?id=WHjO9K6xEm4C&pg=PA269), MIT Press, p. 269, [ISBN](/source/ISBN_(identifier)) [9780262590204](https://en.wikipedia.org/wiki/Special:BookSources/9780262590204).

1. **[^](#cite_ref-2)** [Schrijver, Alexander](/source/Alexander_Schrijver) (1998), [*Theory of Linear and Integer Programming*](https://books.google.com/books?id=zEzW5mhppB8C&pg=PA19), Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19, [ISBN](/source/ISBN_(identifier)) [9780471982326](https://en.wikipedia.org/wiki/Special:BookSources/9780471982326).

1. **[^](#cite_ref-3)** Homer, Steven; [Selman, Alan L.](/source/Alan_Selman) (2011), *Computability and Complexity Theory*, Texts in Computer Science, Springer, [ISBN](/source/ISBN_(identifier)) [9781461406815](https://en.wikipedia.org/wiki/Special:BookSources/9781461406815).

1. **[^](#cite_ref-4)** Singh, Arindama (2009), [*Elements of Computation Theory*](https://books.google.com/books?id=gqWMGR1otqoC&pg=PA287), Texts in Computer Science, Springer, Exercise 9.10, p. 287, [ISBN](/source/ISBN_(identifier)) [9781848824973](https://en.wikipedia.org/wiki/Special:BookSources/9781848824973).

1. **[^](#cite_ref-5)** Bovet, Daniele; Crescenzi, Pierluigi (1994), *Introduction to the Theory of Complexity*, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, [ISBN](/source/ISBN_(identifier)) [9780139153808](https://en.wikipedia.org/wiki/Special:BookSources/9780139153808).

1. **[^](#cite_ref-6)** Vollmer, Heribert (1999), [*Introduction to Circuit Complexity: A Uniform Approach*](https://books.google.com/books?id=55ZTgOJs8bsC&pg=PA113), Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113, [ISBN](/source/ISBN_(identifier)) [9783540643104](https://en.wikipedia.org/wiki/Special:BookSources/9783540643104).

1. **[^](#cite_ref-7)** Pruim, R.; Wegener, Ingo (2005), [*Complexity Theory: Exploring the Limits of Efficient Algorithms*](https://books.google.com/books?id=LXPVrcsdAyYC&pg=PA66), Springer, p. 66, [ISBN](/source/ISBN_(identifier)) [9783540274773](https://en.wikipedia.org/wiki/Special:BookSources/9783540274773).

1. **[^](#cite_ref-8)** Ausiello, Giorgio (1999), [*Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties*](https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA189), Springer, p. 189, [ISBN](/source/ISBN_(identifier)) [9783540654315](https://en.wikipedia.org/wiki/Special:BookSources/9783540654315).

---
Adapted from the Wikipedia article [Complement (complexity)](https://en.wikipedia.org/wiki/Complement_(complexity)) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Complement_(complexity)?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.