Search problem
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Search_problem".

In computability theory, a search problem is a type of computational problem represented by a binary relation. If R is a binary relation such that field(R) ⊆ Γ⁺ 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 graph of a partial function is a binary relation, and if T calculates a partial function then there is at most one possible output.

A relation 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

.

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).

This article incorporates material from search problem on PlanetMath, which is licensed under the GFDL.