Complement (complexity): Difference between revisions

Revision as of 10:25, 10 October 2016

Revision as of 21:23, 6 August 2021

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.&nbsp;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.