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

Definition

PlanetMath defines the problem as follows:

is a Turing machine calculates if:

• need only find one of them)

• .

• Note that the graph of a partial function calculates a partial function then there is at most one possible output.

  can be viewed as a search problem is also said to solve it. Every search problem has a corresponding decision problem

  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

References