1
$\begingroup$

How do we differentiate these classes of problems?

|cite|improve this question
$\endgroup$

closed as unclear what you're asking by David Richerby, Rick Decker, Evil, Juho, Yuval Filmus May 14 '17 at 17:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 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$.

|cite|improve this answer
$\endgroup$
2
$\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.

|cite|improve this answer
$\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.

|cite|improve this answer
$\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.