Content deleted Content added
m →top: http→https for Google Books and Google News using AWB |
comment on probabilistic classes closed under complement |
||
| (One intermediate revision by one other user not shown) | |||
Line 1:
In [[computational complexity theory]], the '''complement''' of a [[decision problem]] is the decision problem resulting from reversing the ''yes'' and ''no'' answers.<ref>{{citation|title=Encyclopedic Dictionary of Mathematics, Volume 1|first=Kiyosi|last=Itô|publisher=MIT Press|year=1993|isbn=9780262590204|url=https://books.google.com/books?id=WHjO9K6xEm4C&pg=PA269|page=269}}.</ref> Equivalently, if we define decision problems as sets of finite strings, then the [[complement (set theory)|complement]] of this set over some fixed ___domain is its complement problem.<ref>{{citation|title=Theory of Linear and Integer Programming|series=Wiley Series in Discrete Mathematics & Optimization|first=Alexander|last=Schrijver|publisher=John Wiley & Sons|year=1998|isbn=9780471982326|url=https://books.google.com/books?id=zEzW5mhppB8C&pg=PA19|page=19}}.</ref>
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.<ref>{{citation|title=Computability and Complexity Theory|series=Texts in Computer Science|first1=Steven|last1=Homer|first2=Alan L.|last2=Selman|author2-link=Alan Selman|publisher=Springer|year=2011|isbn=9781461406815}}.</ref>
There is a [[Turing reduction]] from every problem to its complement problem.<ref>{{citation|title=Elements of Computation Theory|series=Texts in Computer Science|first=Arindama|last=Singh|publisher=Springer|year=2009|isbn=9781848824973|at=Exercise 9.10, p. 287|url=https://books.google.com/books?id=gqWMGR1otqoC&pg=PA287}}.</ref> The complement operation is an [[Involution (mathematics)|involution]], meaning it "undoes itself", or the complement of the complement is the original problem.
Line 12:
Every deterministic complexity class ('''DSPACE'''(f(n)), '''DTIME'''(f(n)) for all f(n)) is closed under complement,<ref>{{citation|title=Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties|first=Giorgio|last=Ausiello|publisher=Springer|year=1999|isbn=9783540654315|page=189|url=https://books.google.com/books?id=Yxxw90d9AuMC&pg=PA189}}.</ref> 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 (complexity)|BPP]], [[ZPP (complexity)|ZPP]], [[BQP]] or [[PP (complexity)|PP]] which are defined symmetrically with regards to their ''yes'' and ''no'' instances are closed under complement. In contrast, classes such as [[RP (complexity)|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 (complexity)|NL]] and [[SL (complexity)|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 (complexity)|L]]''', which is a deterministic class.
| |||