Search problem

Template:Multiple issues 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 Template:Mvar where Template:Mvar if and only if "Template:Mvar is an admissible answer given Template:Mvar".<ref group="note" name="admissible"/> 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 Template:Mvar, it returns an admissible answer Template:Mvar for Template:Mvar when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for Template:Mvar with no such answer.

Definition

PlanetMath defines the problem as follows:<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}Template:Creative Commons text attribution notice</ref>

If <math>R</math> is a binary relation such that <math>\operatorname{field}(R)\subseteq\Gamma^{+}</math> and <math>T</math> is a Turing machine, then <math>T</math> calculates <math>f</math> if:<ref group="note" name="def-henry-405"/>

• If <math>x</math> is such that there is some <math>y</math> such that <math>R(x,y)</math> then <math>T</math> accepts <math>x</math> with output <math>z</math> such that <math>R(x,z)</math>. (there may be multiple <math>y</math>, and <math>T</math> need only find one of them)
• If <math>x</math> is such that there is no <math>y</math> such that <math>R(x,y)</math> then <math>T</math> rejects <math>x</math>.

Note that the graph of a partial function is a binary relation, and if <math>T</math> calculates a partial function then there is at most one possible output.

A <math>R</math> can be viewed as a search problem, and a Turing machine which calculates <math>R</math> is also said to solve it. Every search problem has a corresponding decision problem, namely <math>L(R)=\{x\mid \exists y R(x,y)\}.</math>

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

References

Template:Reflist {{#if: | This article incorporates material from the following PlanetMath articles, which are licensed under the Creative Commons Attribution/Share-Alike License: {{#if: | search problem | {{#if: 3425 | search problem | [{{{sourceurl}}} search problem] }} }}, {{#if: | {{{title2}}} | {{#if: | {{{title2}}} | [{{{sourceurl2}}} {{{title2}}}] }} }}{{#if: | , {{#if: | {{{title3}}} | {{#if: | {{{title3}}} | [{{{sourceurl3}}} {{{title3}}}] }} }} }}{{#if: | , {{#if: | {{{title4}}} | {{#if: | {{{title4}}} | [{{{sourceurl4}}} {{{title4}}}] }} }} }}{{#if: | , {{#if: | {{{title5}}} | {{#if: | {{{title5}}} | [{{{sourceurl5}}} {{{title5}}}] }} }} }}{{#if: | , {{#if: | {{{title6}}} | {{#if: | {{{title6}}} | [{{{sourceurl6}}} {{{title6}}}] }} }} }}{{#if: | , {{#if: | {{{title7}}} | {{#if: | {{{title7}}} | [{{{sourceurl7}}} {{{title7}}}] }} }} }}{{#if: | , {{#if: | {{{title8}}} | {{#if: | {{{title8}}} | [{{{sourceurl8}}} {{{title8}}}] }} }} }}{{#if: | , {{#if: | {{{title9}}} | {{#if: | {{{title9}}} | [{{{sourceurl9}}} {{{title9}}}] }} }} }}. | This article incorporates material from {{#if: | search problem | search problem}} on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License. }}