2
$\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.

Improve this question
$\endgroup$
2
  • $\begingroup$ en.wikipedia.org/wiki/Search_problem $\endgroup$
    – D.W. ♦
    Commented Mar 18, 2019 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
    Commented Mar 18, 2019 at 23:49

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Mar 19, 2019 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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