Optimization version of decision problems

It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem

• optimization/search version:

Given an undirected unweighted graph $G = (V, E)$ and two vertices $v,u\in V$, find a shortest path between $v$ and $u$.

• decision version:

Given an undirected unweighted graph $G = (V, E)$, two vertices $v,u\in V$, and a non-negative integer $k$, is there a path in $G$ between $u$ and $v$ whose length is at most $k$?


In general, "Find $x^\in X$ s.t. $f(x^) = \min\{f(x)\mid x\in X\}$!" becomes "Is there $x\in X$ s.t. $f(x) \leq k$?".

But is the reverse also true, i.e. is there an equivalent optimization problem for every decision problem? If not, what is an example of a decision problem that has no equivalent optimization problem?

As already stated in the comments, it depends on the definitions, as usual. My attempt to answer this needs quite a few definitions, so this will be another example of my inability to give concise answers.

Definition: An optimization problem is a tuple $(X,F,Z,\odot)$ with

• $X$ the set of suitably encoded (strings) instances or inputs.

• $F$ is a function that maps each instance $x\in X$ to a set $F(x)$ of feasible solutions of $x$.

• $Z$ is the objective function that maps each pair $(x, y)$, where $x \in X$ and $y\in F(x)$, to a real number $Z(x, y)$ called the value of $y$.

• $\odot$ is the optimization direction, either $\min$ or $\max$.

Definition: An optimal solution of an instance $x\in X$ of an optimization problem $P_O$ is a feasible solution $y\in F(x)$ for which $Z(x, y)=\odot\{Z(x, y')\mid y'\in F(x)\}$. The value of an optimal solution is denoted with $Opt(x)$ and called the optimum.

Definition: The evaluation problem, denoted $P_E$, corresponding to the optimization problem $P_O$ is the following: Given an instance $x\in X$, compute $Opt(x)$ if $x$ has an optimal solution and output “no optimal solution” otherwise.

Note that this just asks for the value of the optimal solution not the whole solution itself with all its details.

Definition: The decision problem, denoted $P_D$ corresponding to the optimization problem $P_O$ is the following: Given a pair $(x, k)$, where $x\in X$ and $k\in\mathbb{Q}$, decide whether $x$ has a feasible solution $y$ such that $Z(x, y)\le k$ if $\odot=\min$ and such that $Z(x, y)\ge k$ if $\odot=\max$.

A first observation is now that $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$. The proof is not difficult and omitted here.

Now intuitively $P_E$ and $P_D$ corresponding to $P_O$ are not more difficult than $P_O$ itself. To express this feeling formally (thereby defining what equivalent is supposed to mean) we will use reductions.

Recall that a language $L_1$ is polynomial-time reducible to another language $L_2$ if there is a function $f$, computable in polynomial time, such that for all words $x$, $x\in L_1\Leftrightarrow f(x)\in L_2$. This kind of reducibility is known as Karp or many-to-one reducibility, and if $L_1$ is reducible to $L_2$ in this manner, we express this by writing $L_1\le_m L_2$. This is a central concept in the definition of NP-completness.

Unfortunately, many-to-one reductions go between languages and it is not clear how to employ them in the context of optimization problems. Therefore we need to consider a different kind of reducibility, Turing reducibility. First we need this:

Definition: An oracle for a problem $P$ is a (hypothetical) subroutine that can solve instances of $P$ in constant time.

Definition: A problem $P_1$ is polynomial-time Turing-reducible to a problem $P_2$, written $P_1\le_T P_2$, if instances of $P_1$ can be solved in polynomial time by an algorithm with access to an oracle for $P_2$.

Informally, just as with $\le_m$, the relation $P_1\le_T P_2$ expresses, that $P_1$ is no more difficult than $P_2$. It is also easy to see that if $P_2$ can be solved in polynomial time, so can $P_1$. Again $\le_T$ is a transitive relation. The following fact is obvious:

Let $P_O\in \mathrm{NPO}$, then $P_D\le_T P_E\le_T P_O$.

Because given the full solution, computing its value and deciding whether it meets the bound $k$ is simple.

Definition: If for two problems $P_1$ and $P_2$ both relations $P_1\le_T P_2$, $P_2\le P_1$ hold, we write $P_1\equiv_T P_2$; our notion of equivalence.

We are now ready to proof that $P_D\equiv_T P_E$ given the corresponding optimization problem is $P_O\in \mathrm{NPO}$ and $Z$ is integer valued. We have to show that $P_E \le_T P_D$ holds. We can determine $\odot\{Z(x,y)\mid y\in F(x)\}$ with a binary search usign the orcale for $P_D$. The definition of $\mathrm{NPO}$ ensures that $|Z(x, y)|\le 2^{q(|x|)}$ for some polynomial $q$, so the number of steps in the binary search is polynomial in $|x|$. $\Box$

For an optimization problem $P_O$ the relation to $P_E$ is less clear. In many concrete cases, one can show directly that $P_D\equiv_T P_E \equiv_T P_O$. To prove that this holds generally within the framework given here we need an additional assumption.

First we need to extend $\le_m$ from pairs of languages to pairs of the corresponding decision problems. Then it is easy to see that $\le_T$ is more general than $\le_m$.

Let $P$ and $P'$ be decision problems; then $P\le_m P' \Rightarrow P\le_T P'$. This holds because a many-to-one reduction can be interpreted as making use of an oracle in a very restricted way: The oracle is called once, at the very end, and its result is also returned as the overall result. $\Box$

Now we are ready for the finale:

Let $P_O\in \mathrm{NPO}$ and suppose $Z$ is integer-valued and that $P_D$ is NP-complete, then $$P_D\equiv_T P_E \equiv_T P_O.$$ With the previous observations it remains to show $P_O\le_T P_E$. To do this we will exhibit a problem

StackExchange Computer Science Q#939, answer score: 33