Related Searches
Definitions

# 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

$L\left(R\right)=\left\{xmid exists y R\left(x,y\right)\right\}$.

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

Search another word or see search problemon Dictionary | Thesaurus |Spanish