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.

Non-Semi-Decidability by Reduction

Non-Semi-Decidability

To show that a problem is not semi-decidable, reduce the co-halting problem to it. If the target problem were semi-decidable, then the co-halting problem would be semi-decidable as well.

If ${\mathcal{P}}_1\le {\mathcal{P}}_2$, then $\text{co-}{\mathcal{P}}_1\le \text{co-}{\mathcal{P}}_2$.

Non-Semi-Decidability

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

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

Indirect Proof

We want to show:

$$\mathcal{P}\text{ semi-decidable},\mathcal{P}\text{ undecidable}⊢\neg (\text{co-}\mathcal{P}\text{ semi-decidable})$$

where $⊢$ means that the assumptions entail the conclusion. See sequent calculus.

Assume that $\mathcal{P}$ is semi-decidable and $\mathcal{P}$ is undecidable. Then $\text{co-}\mathcal{P}$ is not semi-decidable, because if $\text{co-}\mathcal{P}$ were also semi-decidable, then the theorem above would imply that $\mathcal{P}$ is decidable. This is a contradiction.