Co Decision Problem

computation

Definition

Co-Decision Problem

A co decision problem of a decision problem is a decision problem that represents the complement (negation) of .

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

Properties

Decidability

Decidability and

Trivially, if a decision problem is decidable if and only if is decidable, and vice versa.

Let be a program that decides . Then there exists a program that negates the output of , i.e. , and vice versa.

Dual Semi-Decidability

Dual Semi-Decidability and

Let and be semi-decidable. It follow that and thus are decidable.

A program can be constructed the aborts the respective infinite loop of or 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 , then .

Non-Semi-Decidability

Undecidability of and Semi-Decidability

Let be undecidable and semi-decidable. Then is not semi-decidable.

Indirect Proof

We want to show:

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

Assume that is semi-decidable and is undecidable. Then is not semi-decidable, because if were also semi-decidable, then the theorem above would imply that is decidable. This is a contradiction.