Definition. decision problem [decision-problem]

A decision problem is a computational problem with a Boolean / binary / n-ary output.

We can usually tweak computational problems to become decision problems: e.g. given (x,y)\left( {x,y} \right), does xx have a prime factor that is <y< y?

Important Idea: decision problems are equivalent to languages.

Example.

Let ff be a decision problem. Let LL be the set of all strings that ff maps to “Yes”.

L={x∈Σ*:f(x)=Yes}L = \left\{ {x \in \Sigma \ast :f(x) = \text{Yes}} \right\}T={x∈Σ*:f(x)=No}T = \left\{ {x \in \Sigma \ast :f(x) = \text{No}} \right\}

LL and TT are complementary sets: no element is in both, and every element (of the overarching language) is in one or the other.

Example.

L={x∈Σ*:xis prime}L = \left\{ {x \in \Sigma \ast :x\ \text{is prime}} \right\}

The decision problem is f(x)={Yes ifxis prime; No otherwise}f(x) = \left\{ {\text{Yes if}\ x\ \text{is prime; No otherwise}} \right\}