search problem vs optimization problem

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?

• 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. – Pontus Aug 24 '18 at 8:43
• @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”. – user56834 Aug 24 '18 at 9:40
• 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. – Pontus Aug 24 '18 at 9:59

• @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"). – orlp Aug 25 '18 at 10:35