Search problem

2022-02-13 18:17:56

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: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) If x is such that there is no y such that R(x, y) then T rejects x

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: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) If x is such that there is no y such that R(x, y) then T rejects x
Read article on Wikipedia