Search problem

{{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 {{mvar|R}} where {{mvar|xRy}} if and only if "{{mvar|y}} is an admissible answer given {{mvar|x}}". 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 {{mvar|x}},

it returns an admissible answer {{mvar|y}} for {{mvar|x}} when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for {{mvar|x}} with no such answer.

Definition

PlanetMath defines the problem as follows:{{cite web |title=PlanetMath |url=https://planetmath.org/searchproblem |website=planetmath.org |access-date=15 May 2025}}{{Creative Commons text attribution notice|cc=by2.5|from this source=yes}}

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.

: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 \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).

Notes

{{reflist|group=note|refs=

Luca Trevisan (2010), [https://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf Stanford University - CS254: Computational Complexity, Handout 2 ], p. 1.

Henry, [https://planetmath.org/searchproblem PlanetMath.org - search problem].

}}

References

Category:Computational problems

Search problem

Definition

See also

Notes

References