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.
  • If is such that there is no such that then rejects.