Decision problems, search problems, and function problems

Fix a set $I$ of instances together with an effective binary encoding $\sigma :I\to \{0,1{\}}^{\ast }$ (Effective binary encodings and total decoders).

A decision problem on $I$ is a distinguished subset $Y\subseteq I$ of yes-instances. Its associated language of encoded yes-instances is $L_{\sigma }(Y):=\{\sigma (x):x\in Y\}\subseteq \{0,1{\}}^{\ast },$ a language over the binary alphabet in the sense of Languages over an alphabet.

A search problem on $I$ consists of a condition assigning to each instance $x\in I$ a set of acceptable outputs; solving the problem means producing one acceptable output when one exists.

A function problem on $I$ is a specified total function on instances, $f:I\to O,$ for some output set $O$ (A function is a relation $f$ with $(a,b)\in f$ and $(a,c)\in f$ implying $b=c$; $f:A\to B$, the value $f(a)$, domain and codomain).

• Decision problems ask for a yes/no answer, search problems ask for a witness, and function problems ask for a designated output value.

• The same mathematical problem can have several encodings. The associated language depends on the chosen $\sigma$.