principleMinor
search problem vs optimization problem
Viewed 0 times
problemoptimizationsearch
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#96567, answer score: 3
Revisions (0)
No revisions yet.