Co Decision Problem

computation

Definition

Co-Decision Problem

A co decision problem $\text{co-}\mathcal{P}$ of a decision problem $\mathcal{P}$ is a decision problem that represents the complement (negation) of $\mathcal{P}$.

Example: SAT (decision problem) vs UNSAT (co decision problem)

Properties

Decidability

Decidability $\mathcal{P}$ and $\text{co-}\mathcal{P}$

Trivially, if a decision problem $\mathcal{P}$ is decidable if and only if $\text{co-}\mathcal{P}$ is decidable, and vice versa.

Let $\Pi$ be a program that decides $\mathcal{P}$. Then there exists a program ${\Pi }^{\prime }$ that negates the output of $\Pi$, i.e. ${\Pi }^{\prime }(\dots )=\neg \Pi (\dots )$, and vice versa.

Dual Semi-Decidability

Dual Semi-Decidability $\mathcal{P}$ and $\text{co-}\mathcal{P}$

Let $\mathcal{P}$ and $\text{co-}\mathcal{P}$ be semi-decidable. It follow that $\mathcal{P}$ and thus $\text{co-}\mathcal{P}$ are decidable.

A program ${\Pi }^{\prime }$ can be constructed the aborts the respective infinite loop of ${\Pi }_{\mathcal{P}}$ or ${\Pi }_{\text{co-}\mathcal{P}}$ if the other one outputs.

Undecidability and Semi-Decidability

Undecidability of $\mathcal{P}$ and Semi-Decidability $\mathcal{P}$

Let $\mathcal{P}$ be undecidable (1) and semi-decidable (2). Then $\text{co-}\mathcal{P}$ is not semi-decidable.

Indirect Proof: Assume that $\text{co-}\mathcal{P}$ is semi-decidable, i.e. $\mathcal{P}$ and $\text{co-}\mathcal{P}$ are both semi-decidable. Then from this theorem follows that $\mathcal{P}$ is decidable. This is a contradiction (1).