A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.

Search problems are a class of computational problems. Generally a search problem is of the form:

Given input $x$,
Find a $y$ such that $R(x,y)$ holds.

where $R$ is a binary relation. The $y$ does not need to be unique. By putting restrictions on the possible $y$s and the computational complexity of $R$ we obtain various class of search problems.

An example of a search problem:

Given a graph $G$,
Find a $C$ which is a maximal clique in $G$.

For algorithms for searching for an object satisfying a property please use the tags and .

history | excerpt history