Editing Search problem

{{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 [[Matching (graph theory)|matchings]], optional [[clique (graph theory)|cliques]], and [[Independent set (graph theory)|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.

:A <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]]