Editing Complexity class (section)

===Closure===
Complexity classes have a variety of [[Closure (mathematics)|closure]] properties. For example, decision classes may be closed under [[negation]], [[disjunction]], [[Logical conjunction|conjunction]], or even under all [[Logical connective|Boolean operations]]. Moreover, they might also be closed under a variety of quantification schemes. '''P''', for instance, is closed under all Boolean operations, and under quantification over polynomially sized domains. Closure properties can be helpful in separating classes—one possible route to separating two complexity classes is to find some closure property possessed by one class but not by the other.

Each class '''X''' that is not closed under negation has a complement class '''co-X''', which consists of the complements of the languages contained in '''X''' (i.e. <math>\textsf{co-X} = \{L| \overline{L} \in \mathsf{X} \}</math>). '''[[co-NP]]''', for instance, is one important complement complexity class, and sits at the center of the unsolved problem over whether '''co-NP'''='''NP'''.

Closure properties are one of the key reasons many complexity classes are defined in the way that they are.{{sfn|Aaronson|2017|p=7}} Take, for example, a problem that can be solved in <math>O(n)</math> time (that is, in linear time) and one that can be solved in, at best, <math>O(n^{1000})</math> time. Both of these problems are in '''P''', yet the runtime of the second grows considerably faster than the runtime of the first as the input size increases. One might ask whether it would be better to define the class of "efficiently solvable" problems using some smaller polynomial bound, like <math>O(n^3)</math>, rather than all polynomials, which allows for such large discrepancies. It turns out, however, that the set of all polynomials is the smallest class of functions containing the linear functions that is also closed under addition, multiplication, and composition (for instance, <math>O(n^3) \circ O(n^2) = O(n^6)</math>, which is a polynomial but <math>O(n^6)>O(n^3)</math>).{{sfn|Aaronson|2017|p=7}} Since we would like composing one efficient algorithm with another efficient algorithm to still be considered efficient, the polynomials are the smallest class that ensures composition of "efficient algorithms".{{sfn|Aaronson|2017|p=5}} (Note that the definition of '''P''' is also useful because, empirically, almost all problems in '''P''' that are practically useful do in fact have low order polynomial runtimes, and almost all problems outside of '''P''' that are practically useful do not have any known algorithms with small exponential runtimes, i.e. with <math>O(c^n)</math> runtimes where {{mvar|c}} is close to 1.{{sfn|Aaronson|2017|p=6}})