Decidable Decision Problem

computation

Definition

Decidable Decision Problem

A decision problem $\mathcal{P}$ is called decidable if there exists an algorithm $\Pi$ that takes any instance $x$ of the problem as input and produces the correct answer yes/no (or isomorphic representations, such as 1/0 or true/false) as output. In particular, such an algorithm terminates on every instance.

Co-Problem

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)

Link to original