1
$\begingroup$

How do we differentiate these classes of problems?

$\endgroup$
  • 2
    $\begingroup$ We expect you to do some basic research before asking a question here. Even looking up the definitions of those classes will tell you what the differences between them are. $\endgroup$ – David Richerby May 8 '17 at 8:43
5
$\begingroup$

A decision problem has this form:

  • Input: $x$
  • Output: "Yes" if $\phi(x)$ holds, "No" otherwise

A search problem has this form:

  • Input $x$

  • Output: $y$ such that $\psi(x,y)$ holds, if such a $y$ exists. "No" otherwise.

Finally, an optimization problem has this form:

  • Input $x$

  • Output: $y$ such that $f(x,y)$ is the minimum possible, i.e. $f(x,y) = \min_{y'} f(x,y')$

Here $\phi$ and $\psi$ are some boolean properties, and $f$ is some natural number function of $x$ and $y$.

$\endgroup$
1
$\begingroup$

In a search problem you are looking for something.
In an optimization problem you want to find the best way to do something.
In a decision problem you are trying to decide whether something is true.

I suspect the reason you asked this question is that optimization or decision problems might be implementable in terms of a search problem. For example, if you are trying to decide whether a graph has some property, you might have to traverse (search) it.

$\endgroup$
0
$\begingroup$

Decision problem

Input is a question where the output is yes or no. Output is yes or no from the algorithm.

Search problem

This problem usually has several parts: Building a corpus, doing inserts and doing lookups. A common problem is to organize the data so that lookups can be done fast.

Optimization problem

Provided a constraint, for example x + y < 10, optimize some formula for example x*y and find its maximum or minimum value.

$\endgroup$
  • $\begingroup$ This answer conflates "search problems" with a specific problem in "information retrieval." Search is a far more general concept (for example, when we ask a robot to navigate to a particular part of the room, or to solve a jigsaw puzzle, we are posing a search problem). $\endgroup$ – SigmaX Apr 30 '18 at 18:18

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