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
See more at Wikipedia.org...

<computability> A computational problem that requires identifying a solution from some, possibly infinite, solution space (set of possible solutions). E.g. "What is the millionth prime number?". This contrasts with a decision problem which merely asks whether a given answer is a solution or not.
(1999-02-15)