Complement Complexity Class

complexity-theory

Definition

Complement Complexity Class

Let $\mathcal{C}$ be a complexity class of decision problems. The complement class of $\mathcal{C}$ is the class

$$\mathrm{co}\text{-}\mathcal{C}=\{\overline{\mathcal{P}}\mid \mathcal{P}\in \mathcal{C}\},$$

where $\overline{\mathcal{P}}$ is the co-decision problem of $\mathcal{P}$.

Equivalently, $\mathrm{co}\text{-}\mathcal{C}$ contains exactly the complements of the problems in $\mathcal{C}$.

Examples: $\mathrm{co}\text{-}\mathrm{P}$, $\mathrm{co}\text{-}\mathrm{NP}$, $\mathrm{co}\text{-}\mathrm{EXPTIME}$.

Properties

• For deterministic classes, the class is often closed under complement, so $\mathrm{P}=\mathrm{co}\text{-}\mathrm{P}$.
• For nondeterministic classes, closure under complement is generally unknown or false; for example, whether $\mathrm{NP}=\mathrm{co}\text{-}\mathrm{NP}$ is open.
• If a class $\mathcal{C}$ is closed under complement, then every problem in $\mathcal{C}$ has its complement also in $\mathcal{C}$.