Search problem

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(R)={xmid 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).

Search another word or see search problemon Dictionary | Thesaurus |Spanish
Copyright © 2015, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature