search problem

If R is a binary relationMathworldPlanetmath such that field(R)Γ+ and T is a Turing machineMathworldPlanetmath, 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 functionMathworldPlanetmath 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 problemMathworldPlanetmath, namely L(R)={xyR(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 2013-03-22 13:01:39
Last modified on 2013-03-22 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