Search problem

In computational complexity theory and 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 R if:

Intuitively, the problem consists in finding structure "y" in object "x". An algorithm is said to solve the problem if at least one corresponding structure exists, and then one occurrence of this structure is outputted; otherwise, the algorithm stops with an appropriate output ("Item not found" or any message of the like).