# What is a search problem?

I'm looking for a formal and broad definition.

Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a problem requires multiple checks?

Alternatively, I also think intuitively of problems with multiple paths as a search problem. In this case, only a single check might be necessary but multiple comparisons are needed in order to know which path is the best to follow.

• en.wikipedia.org/wiki/Search_problem
– D.W.
Mar 18, 2019 at 23:34
• Thanks for the link, but it is a poorly written. For example, it uses the symbol Γ without explaining its meaning. I went to the Turing Machine article but couldn't find that symbol in the whole article. Mar 18, 2019 at 23:49

A problem is a search problem if there's an algorithmic way to verify the answer. In particular, let $$V$$ be any algorithm that takes two inputs and always terminates. Then the following is a search problem:
Input: $$x$$
Goal: find and output any $$y$$ such that $$V(x,y)=1$$, or report that no such $$y$$ exists
Every search problem can be written in this form. In particular, you can take the above as the definition of a search problem: a problem is a search problem if there exists an always-terminating algorithm $$V$$ that has the above form.
• Note that technically any problem can be defined as a search problem. E.g. a decision problem can be defined as $V(x, 0) = 1$ when $x$ is a false instance and $V(x, 1) = 1$ when $x$ is a true instance. But this is contrived, you should apply common sense when determining what kind of problem something is.