= Computational problem
{wiki}
A <computational problem> specifies what counts as a valid <output> for each permitted <input>. A <binary relation> $R\subseteq I\times O$ can express this requirement: $(x,y)\in R$ means that $y$ is a valid answer to $x$. The <computational problem> is the specification; an <algorithm> is a proposed way to satisfy it.
For example, given an <array> $A$ and value $v$, under the promise that $v$ occurs, a <search problem> can request any index $i$ with $A_i=v$. Repeated values may give several valid <outputs>. The related <decision problem> only asks whether an occurrence exists and requires a yes-or-no answer. Stating the encoding, permitted instances and required answer prevents these tasks from being confused when comparing <running time> or verification costs.
Back to article page
