4
$\begingroup$

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question

As I understand it, we can define the two as follows (note, I consider the problem for a fixed input size for brevity):

Search problem. Given a set $X$ of candidate solutions, and a property $P:X\to \{\text{True}, \text{False}\}$, find an $x\in X$ such that $P(x)$.

Optimization problem. Given a set $X$ of candidate solutions, and a criterion function $F:X\to \mathbb R$, find an $x\in X$ such that $x\in \arg\max_{y\in X} F(y)$.

But it seems to me that to say that a search problem $P_S$ is "reducible" to an optimization problem $P_O$ is an understatement: They seem to be exactly the same apart from a "stylistic" difference:

Given a search problem $P_S=(X,P)$, define optimization problem $P_O=(X,F)$ where $F(x) = \begin{cases}1 \quad \text {if } P(x)\\0\quad \text {if } \neg P(x) \end{cases}$

Given a optimization problem $P_O=(X,F)$, define search problem $P_S=(X,P)$, with $P(x)= \begin{cases}\text{True} \quad \text { if } x \in \arg\max_{y\in X} F(y)\\\text{False}\quad \text { if } x \notin \arg\max_{y\in X} F(y)\end{cases}$

Is there really not a fundamental difference between these two problems? Or are they fundamentally different in some way that I'm overlooking?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ You are right that one can cast one in terms of another, but that doesn't mean it is always useful to do so. Your rephrasing of a search problem as an optimization problem is simple enough, but the other way around doesn't seem very useful as $P(x)$ will be difficult to evaluate. When talking about search problems, it is often (though not necessarily) implied that the difficulty comes mainly from the searching, not in recognizing the solution once it is found. In general, many definitions could be expressed in terms of other definitions, but they still help us communicate and reason. $\endgroup$ – Pontus Aug 24 '18 at 8:43
  • $\begingroup$ @Pontus, Thank you that’s clarifying for me. It would help me to make this more precise: Does it make sense to say that “typically”, the key difference between the two is as follows: In a search problem, checking property $P$ does not require us to know what the search space is (it is a property of the specific element, not of its relation to the search space), whereas in an optimization problem, we are required to know about every element in the search space to decide whether $x$ has the “optimum property”. $\endgroup$ – user56834 Aug 24 '18 at 9:40
  • $\begingroup$ I think that is a good way of putting it. At least it matches how I tend to think about it, I dare not say if it is representative. $\endgroup$ – Pontus Aug 24 '18 at 9:59
2
$\begingroup$

The fundamental difference in these two problems lies in the verification of a proposed solution.

The solution of a search problem is only as hard to verify correct as the predicate itself.

The solution of an optimization problem needs special arguments or proofs to avoid having to search the entire domain to verify a solution correct, which often may not exist or are not known.

This means that simply finding a solution is enough for a search problem, but without a proof or exhaustive search an instance for an optimization problem is uncertain.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But as shown in the question, it is possible to define a search problem where evaluating the predicate also requires a holistic view if the search space. Formulating a problem as one or the other is more about convention and simplicity, I would say. $\endgroup$ – Pontus Aug 25 '18 at 10:30
  • $\begingroup$ @Pontus It only appears that way because the predicate references a set which happens to also be the same set that is the search space. This is an arbitrary choice, you can even require a holistic view of a space much larger than the search space, such as: "Find an integer $n$ such that for all real $x, y$ we have $x^n = y^n$". This still doesn't change the fact that given such an instance you only have to verify that instance rather than the product of the search space and whatever space(s) the predicate specifies, which the optimization problem requires (e.g. "find the smallest integer"). $\endgroup$ – orlp Aug 25 '18 at 10:35
-1
$\begingroup$

I think search problem is to search for a solution (or many solutions) that satisfies a condition. Whereas, Optimization problem is to search for the best solution that satisfies a condition. When the search space becomes large, we can't expect to be able to find out the optimal solution, then we turn the search problem into an optimization problem, with the hope that as searching for the best solution we may find some acceptable one. By doing so, we are using the optimization techniques which do not promise to find the optimal solution, instead of using the search techniques, which always do.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to CS@SE. You described what "we" do faced with an instance of both problem categories mentioned. Can you pinpoint which difference is fundamental (in the problems rather than approaches to solutions, if that distinction is possible)? What do you think of orlp's idea to use the ease of verification for classification? $\endgroup$ – greybeard Nov 30 '19 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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