search problem

A search problem asks you to find and return an actual solution, not just say whether one exists. Where a decision problem answers "is there a needle in this haystack?" with yes or no, the matching search problem says "if there is a needle, hand it to me." "Find a value equal to 7 in this list (and tell me where)" is a search problem; "find an arrangement of these meetings with no overlaps" is a search problem. The output is a witness — a concrete object that proves the answer is yes.

More precisely, a search problem specifies, for each input, a set of acceptable solutions, and asks the algorithm to produce one of them (or to report that none exists). Take satisfiability of a logic formula: the decision version asks "can these clauses all be made true at once?"; the search version asks "give me an assignment of true/false to the variables that makes them all true." A returned assignment can be checked easily — plug it in and see — which is exactly what makes it a witness. Notice the search problem is at least as demanding as the decision one: if you can find a solution, you can certainly answer whether one exists, but knowing one exists need not tell you how to find it.

Search problems are what most real applications actually want. A route-planner that only told you "yes, a short route exists" without showing it would be useless; you want the route. Often a fast decision procedure can be bootstrapped into a search procedure by asking decision questions about pieces of the answer ("must the first step go north?"), but this is a real technique, not a free lunch, and it is part of why the relationship between deciding and searching is studied so carefully.