1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Search_problem $\endgroup$ – D.W. Mar 18 at 23:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Lay González Mar 18 at 23:49
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – orlp Mar 19 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.