Editing Search problem (section)

{{multiple issues|
{{more references|date=May 2025}}
{{more footnotes needed|date=May 2025}}
}}
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]] {{mvar|R}} where {{mvar|xRy}} if and only if "''{{mvar|y}} is an admissible answer given {{mvar|x}}''".<ref group="note" name="admissible"/> Search problems frequently occur in [[graph theory]] and [[combinatorial optimization]], e.g. searching for [[Matching (graph theory)|matchings]], optional [[clique (graph theory)|cliques]], and [[Independent set (graph theory)|stable sets]] in a given undirected graph.

An [[algorithm]] is said to solve a search problem if, for every input value {{mvar|x}}, 
it returns an admissible answer {{mvar|y}} for {{mvar|x}} when such an answer exists; otherwise, it returns any appropriate output, e.g. "not found" for {{mvar|x}} with no such answer.