Definition
Complement Complexity Class
Let
be a complexity class of decision problems. The complement class of is the class where
is the co-decision problem of . Equivalently,
contains exactly the complements of the problems in . Examples:
, , .
Properties
- For deterministic classes, the class is often closed under complement, so
. - For nondeterministic classes, closure under complement is generally unknown or false; for example, whether
is open. - If a class
is closed under complement, then every problem in has its complement also in .