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
1
$\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

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.