Search problem

Template:Multiple issues 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 Template:Mvar where Template:Mvar if and only if "Template:Mvar is an admissible answer given Template:Mvar". 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 Template:Mvar, it returns an admissible answer Template:Mvar for Template:Mvar when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for Template:Mvar with no such answer.

Definition

PlanetMath defines the problem as follows:

If $R$ is a binary relation such that $\mathrm{field}(R)\subseteq {\mathrm{\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.

A $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 \mathrm{\exists }yR(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

References

Template:Reflist This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.