What are the differences between search problems, optimization problems, and decision problems? [closed]

Question

How do we differentiate these classes of problems?

Answer 1

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

Answer 2

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.

Answer 3

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.