search problem
If $R$ is a binary relation^{} such that $\mathrm{field}(R)\subseteq {\mathrm{\Gamma}}^{+}$ and $T$ is a Turing machine^{}, then $T$ calculates $f$ if:

•
If $x$ is such that there is some $y$ such that $R(x,y)$ then $T$ accepts $x$ with output $z$ such that $R(x,z)$ (there may be multiple $y$, and $T$ need only find one of them)

•
If $x$ is such that there is no $y$ such that $R(x,y)$ then $T$ rejects $x$
Note that the of a partial function^{} is a binary relation, and if $T$ calculates a partial function then there is at most one possible output.
A $R$ can be viewed as a search problem, and a Turing machine which calculates $R$ is also said to solve it. Every search problem has a corresponding decision problem^{}, namely $L(R)=\{x\mid \exists yR(x,y)\}$.
This definition may be generalized to $n$ary relations using any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter).
Title  search problem 

Canonical name  SearchProblem 
Date of creation  20130322 13:01:39 
Last modified on  20130322 13:01:39 
Owner  Henry (455) 
Last modified by  Henry (455) 
Numerical id  7 
Author  Henry (455) 
Entry type  Definition 
Classification  msc 68Q25 
Defines  calculate 