How do we differentiate these classes of problems?
-
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
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$.
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.
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.
-
$\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