Search problem

From Quire, the open reference·Class of computational problems·1 min read

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 R where xRy if and only if "y is an admissible answer given x".^[1] 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 x, it returns an admissible answer y for x when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for x with no such answer.

Definition#edit

PlanetMath defines the problem as follows:^[2]

If ${\displaystyle R}$ is a binary relation such that ${\displaystyle \operatorname {field} (R)\subseteq \Gamma ^{+$ and ${\displaystyle T}$ is a Turing machine, then ${\displaystyle T}$ calculates ${\displaystyle f}$ if:^[3]

If ${\displaystyle x}$ is such that there is some ${\displaystyle y}$ such that ${\displaystyle R(x,y)}$ then ${\displaystyle T}$ accepts ${\displaystyle x}$ with output ${\displaystyle z}$ such that ${\displaystyle R(x,z)}$ . (there may be multiple ${\displaystyle y}$ , and ${\displaystyle T}$ need only find one of them)
If ${\displaystyle x}$ is such that there is no ${\displaystyle y}$ such that ${\displaystyle R(x,y)}$ then ${\displaystyle T}$ rejects ${\displaystyle x}$ .

Note that the graph of a partial function is a binary relation, and if ${\displaystyle T}$ calculates a partial function then there is at most one possible output.

An ${\displaystyle R}$ can be viewed as a search problem, and a Turing machine which calculates ${\displaystyle R}$ is also said to solve it. Every search problem has a corresponding decision problem, namely ${\displaystyle L(R)=\{x\mid \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).

Notes#edit

^ Luca Trevisan (2010), Stanford University - CS254: Computational Complexity, Handout 2, p. 1.
^ "PlanetMath". planetmath.org. Retrieved 15 May 2025. This article incorporates text from this source, which is available under the CC BY 2.5 license.
^ Henry, PlanetMath.org - search problem.

References#edit

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

Categories Computational problems

This article is mirrored from “Search problem” on English Wikipedia, revision 1338226318, written by Wikipedia's contributors and licensed CC BY-SA 4.0. Editing it here creates a Quire copy with its own history.

Synced with Wikipedia revision 1338226318 · just now

Search problem

Definition#edit

See also#edit

Notes#edit

References#edit