Complement (complexity)

In computational complexity theory, the complement of a decision problem 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 of this set with respect to the given alphabet is its complement problem (although sometimes some "invalid" strings, which do not represent any problem instance, are excluded).

There is a Turing reduction from every problem to its complement problem. The complement operation is an involution, meaning it "undoes itself", or the complement of the complement is the original problem.

We can generalize this to the complement of a complexity 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.

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 problem 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 reductions, 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 the smallest superset of that class which is closed under complement. If a class is intersected with its complement, we obtain a (possibly empty) subset which is closed under complement. Some interesting problems fall into such intersections, such as the graph isomorphism problem, which is in the intersection of NP and co-NP.