Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Search problem

Class of computational problems

Wikipedia contributorsAdapted for Fathomly · View authors
1 min read
Source updated February 13, 2026

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". 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.

01Definition

PlanetMath defines the problem as follows:

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.
An 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 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).
Watch videos about Search problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Search problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Mu operator

In computability theory, the μ-operator, minimization operator, or unbounded search operator searches for the least natural number with a given property. Adding the μ-operator to the primitive recursive functions makes it possible to define all computable functions.

Decision problem

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes-no question on a set of input values. An example of a decision problem is deciding whether a given natural number is prime.

Optimization problem

In mathematics, engineering, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.