Search problem

From Wikipedia, the free encyclopedia

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(R)=\{x\mid \exists y R(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).

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