Search problem: Difference between revisions
imported>Diannaa add attribution for licensed material and a citation |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Class of computational problems}} | |||
{{multiple issues| | {{multiple issues| | ||
{{more references|date=May 2025}} | {{more references|date=May 2025}} | ||
| Line 12: | Line 13: | ||
[[PlanetMath]] defines the problem as follows:<ref>{{cite web |title=PlanetMath |url=https://planetmath.org/searchproblem |website=planetmath.org |access-date=15 May 2025}}{{Creative Commons text attribution notice|cc=by2.5|from this source=yes}}</ref> | [[PlanetMath]] defines the problem as follows:<ref>{{cite web |title=PlanetMath |url=https://planetmath.org/searchproblem |website=planetmath.org |access-date=15 May 2025}}{{Creative Commons text attribution notice|cc=by2.5|from this source=yes}}</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>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 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) | ||
| Line 19: | Line 20: | ||
: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. | :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. | ||
: | :An <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]]). | :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]]). | ||
| Line 33: | Line 34: | ||
==Notes== | ==Notes== | ||
{{reflist|group=note|refs= | {{reflist|group=note|refs= | ||
<ref name="admissible">Luca Trevisan (2010), [https://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf ''Stanford University - CS254: Computational Complexity, Handout 2'' ], p. 1.</ref> | <ref name="admissible">[[Luca Trevisan]] (2010), [https://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf ''Stanford University - CS254: Computational Complexity, Handout 2'' ], p. 1.</ref> | ||
<ref name="def-henry-405">Henry, [https://planetmath.org/searchproblem ''PlanetMath.org - search problem''].</ref> | <ref name="def-henry-405">Henry, [https://planetmath.org/searchproblem ''PlanetMath.org - search problem''].</ref> | ||
}} | }} | ||
Latest revision as of 18:37, 1 December 2025
Template:Short description Script error: No such module "Unsubst". 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".[note 1] 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:[1]
If is a binary relation such that and is a Turing machine, then calculates if:[note 2]
- 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 .
- Note that the graph of a partial function is a binary relation, and if calculates a partial function then there is at most one possible output.
- An can be viewed as a search problem, and a Turing machine which calculates is also said to solve it. Every search problem has a corresponding decision problem, namely
- 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
<templatestyles src="Reflist/styles.css" />
- ↑ Luca Trevisan (2010), Stanford University - CS254: Computational Complexity, Handout 2 , p. 1.
- ↑ Henry, PlanetMath.org - search problem.
Script error: No such module "Check for unknown parameters".
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".Template:Creative Commons text attribution notice
Script error: No such module "Check for unknown parameters".
This article incorporates material from search problem on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.