Decision Problem

computation

Definition

Decision Problem

A decision problem $\mathcal{P}=⟨D,Y⟩$ is a tuple where $D$ is a set of instances and $Y\subseteq D$ is the set of yes-instances.

Given an instance $x\in D$, the problem asks whether $x\in Y$.

The problem is decidable when there exists a Turing machine that halts on every $w\in {\Sigma }^{\ast }$ and accepts exactly those $w\in L_{\mathcal{P}}$.

Language

Definition

Language of a Decision Problem

Fix a finite alphabet $\Sigma$ and a computable encoding $\mathrm{enc}:D\to {\Sigma }^{\ast }$. The language of a decision problem $\mathcal{P}=⟨D,Y⟩$ with an encoding $\mathrm{enc}$ is

$$L[\mathcal{P},\mathrm{enc}]=\{\mathrm{enc}(x)\mid x\in Y\}\subseteq {\Sigma }^{\ast }.$$

Link to original

Complement

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

Cardinality

Not Every Decision Problem is decidable

A decision problem $\mathcal{P}=⟨D,Y⟩$ with a language $L[\mathcal{P},\mathrm{enc}]$ over a finite alphabet $\Sigma$ can be identified with a function $f:{\Sigma }^{\ast }\to \{0,1\}$, where $0$ means NO and 1 means YES:

$$f:w\mapsto \{\begin{array}{ll}1& \text{if }w\in Y\\ 0& \text{otherwise}\end{array}$$

Since ${\Sigma }^{\ast }$ is countable, the set of all functions ${\Sigma }^{\ast }\to \{0,1\}$ is uncountable. Every algorithm has a finite description and is therefore countable. Hence, there are strictly more decision problems than algorithms, and most decision problems are not decidable.

Link to original