Search problem

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:

If is a binary relation such that and is a Turing machine, then calculates if:

• If is such that there is some such that then accepts with output such that . (there may be multiple , and need only find one of them)
• If is such that there is no such that then rejects .

See also

• Unbounded search operator
• Decision problem
• Optimization problem
• Counting problem (complexity)
• Function problem
• Search games

Notes

References