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

How do we differentiate these classes of problems?

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

• 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). – SigmaX Apr 30 '18 at 18:18