Definition: Computational Problem, Solution

A computational problem (or just problem) \(P\) can be viewed as a triple \[P:=(D, I, Q),\] where \(D\) is a set, called the problem domain, \(I\in D\) is a particular instance of the problem, and \(Q\) is * a question, which can be asked about any one of the instances of \(D\), * which is being asked about the particular instance \(I\), * and the answer of which belongs to a certain set $A$ of answers types.

A solution to $P$ is a partial function $f:D\to A$, $$f(I)=\begin{cases}a&\text{if }\exists a\in A \text{ answering }Q\\\operatorname{undef.}&\text{else}\end{cases}$$

If $A$ equals the set of truth values $A=\mathbb B=\{\text{yes},\text{no}\},$ the problem is called a decision problem.

Definitions: 1 2
Examples: 3

Thank you to the contributors under CC BY-SA 4.0!




  1. Reus, Bernhard: "Limits of Computation", Springer, 2016