Search problem

In computational complexity theory and computability theory, a search problem is a computational problem of finding an admissible answer for a given input value, provided that such an answer exists. In fact, a search problem is specified by a binary relation where if and only if " is an admissible answer given ". Search problems frequently occur in graph theory and combinatorial optimization, e.g. searching for matchings, optional cliques, and stable sets in a given undirected graph. An algorithm is said to solve a search problem if, for every input value , it returns an admissible answer for when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for with no such answer.

In computational complexity theory and computability theory, a search problem is a computational problem of finding an admissible answer for a given input value, provided that such an answer exists. In fact, a search problem is specified by a binary relation where if and only if " is an admissible answer given ". Search problems frequently occur in graph theory and combinatorial optimization, e.g. searching for matchings, optional cliques, and stable sets in a given undirected graph. An algorithm is said to solve a search problem if, for every input value , it returns an admissible answer for when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for with no such answer. ==Definition== PlanetMath defines the problem as follows: If R is a binary relation such that \operatorname{field}(R)\subseteq\Gamma^{+} 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. An 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)=\{x\mid \exists y R(x,y)\}. This definition can be generalized to n-ary relations by any suitable encoding which allows multiple strings to be compressed into one string (for instance by listing them consecutively with a delimiter). ==See also== Unbounded search operator Decision problem Optimization problem Counting problem (complexity) Function problem Search games ==Notes== ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1338226318 under CC BY-SA 4.0; modifications have been made.