{{Short description|Class of computational problems}} {{multiple issues| {{more references|date=May 2025}} {{more footnotes needed|date=May 2025}} }} 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}}''".<ref group="note" name="admissible"/> 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:<ref>{{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}}</ref>
If <math>R</math> is a binary relation such that <math>\operatorname{field}(R)\subseteq\Gamma^{+}</math> and <math>T</math> is a Turing machine, then <math>T</math> ''calculates'' <math>f</math> if:<ref group="note" name="def-henry-405"/>
* If <math>x</math> is such that there is some <math>y</math> such that <math>R(x,y)</math> then <math>T</math> accepts <math>x</math> with output <math>z</math> such that <math>R(x,z)</math>. (there may be multiple <math>y</math>, and <math>T</math> need only find one of them) * If <math>x</math> is such that there is no <math>y</math> such that <math>R(x,y)</math> then <math>T</math> rejects <math>x</math>.
:Note that the graph of a partial function is a binary relation, and if <math>T</math> calculates a partial function then there is at most one possible output.
:An <math>R</math> can be viewed as a ''search problem'', and a Turing machine which calculates <math>R</math> is also said to solve it. Every search problem has a corresponding decision problem, namely <math>L(R)=\{x\mid \exists y R(x,y)\}.</math>
: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== {{reflist|group=note|refs= <ref name="admissible">Luca Trevisan (2010), [https://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf ''Stanford University - CS254: Computational Complexity, Handout 2'' ], p. 1.</ref> <ref name="def-henry-405">Henry, [https://planetmath.org/searchproblem ''PlanetMath.org - search problem''].</ref> }}
==References== {{Reflist}} {{PlanetMath attribution|id=3425|title=search problem}}
Category:Computational problems