Optimization version of decision problems

Question

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?

Answer 1

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 $P_O'\in \mathrm{NPO}$ such that $P_O\le_T P_E'$. Then we have $$P_O\le_T P_E' \le_T P_D'\le_T P_D\le_T P_E.$$ The second and third $\le_T$ hold because of the equivalence of the decision and evaluation version proofed earlier. The third $\le_T$ follows from the NP-completness of $P_D$ and the two facts mentioned before, namely $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$ and $P\le_m P_O' \Rightarrow P\le_T P_O'$.

Now the details: Assume that the feasible solutions of $P_O$ are encoded using an alphabet $\Sigma$ equipped with a total order. Let $w_0, w_1, \ldots$ be the words from $\Sigma^*$ listed in order of nondecreasing length and lexicographic order within the blocks of words with common length. (Thus $w_0$ is the empty word.) For all $y\in\Sigma^*$ let $\sigma(y)$ denote the unique integer $i$ such that $y=w_i$. Both $\sigma$ and $\sigma^{-1}$ can be computed in polynomial time. Let $q$ be a polynomial such that for all $x\in X$ and all $y\in F(x)$ we have $\sigma(y)<2^{q(|x|)}$.

Now the problem $P_O'$ is identical to $P_O$ except for a modified objective function $Z'$. For $x\in X$ and $y\in F(x)$ we take $Z'(x, y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$. $Z'$ is computable in polynomial time thus $P_O'\in \mathrm{NPO}$.

To show that $P_O\le_T P_E'$ we observe that $x$ is feasible for $P_O$ if and only if it is feasible for $P_E'$. We can assume that this is the case, since the opposite case is trivial to handle.

The substituion of $Z'$ for $Z$ is monotonic in the sense that for all $y_1, y_2\in F(x)$, if $Z(x, y_1)<Z(x, y_2)$ then $Z'(x, y_1)<Z'(x, y_2)$. This implies that every optimal solution for $x$ in $P_O'$ is an optimal solution of $x$ in $P_O$. Thus our task reduces to the computation of an optimal solution $y$ of $x$ in $P_O'$.

Querying the oracle for $P_E'$ we can get the value of $Z'(x,y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$. Forming the remainder of this number modulo $2^{q(|x|)}$ yields $\sigma(y)$ from which $y$ can be computed in polynomial time.

Answer 2

As the comments say, the answer depends on the exact definitions. Let me interpret the question in a very basic (even naïve) way.

Let $S$ be some relation, that is $S \subseteq \{ (a,b) \mid a,b \in \Sigma^*\}$.

Now we define a search problem for $S$:

Given $a$, find a $b$ such that $(a,b) \in S$.

and a decision problem for $S$:

Given $(a,b)$ answer whether or not $(a,b) \in S$.

_{(for instance, in the example given in the question, $S$ will hold all the pairs $(u,v,k)$ such that there exists a path between $u$ and $v$ which is shorter than $k$.)}

Note that these two problems are well defined. For this definition, we can ask whether the two problems are "equivalent" for any $S$. In "equivalent" I mean that if one of them is computable (i.e., there exists an algorithm that solves it) than the other one is computable as well. In general, they are not.

Claim 1: Decision implies Search.

Proof: Let $D_S$ be the algorithm that solves the decision problem of $S$. Given an input $a$, We can run $D_S(a,x)$ for any $x\in \Sigma^*$, one after the other, or in parallel. If there exists $b$ such that $(a,b)\in S$, we will eventually find it. If not, the algorithm might not stop$^\dagger$.

Claim 2: Search does not imply Decision.

The reason is that the search algorithm might return a different $b$ than the one we need. That is, for every $a$ there is some $b$ that is very easy to find, but other $b'$ that is not. For instance, let $L$ be some undecidable language, then define $$S = \{ (x,0) \mid x\in \Sigma^*\} \cup \{ (x,1) \mid x \in L\}.$$ For every $x$ the search algorithm can return $0$. But no decision algorithm can answer correctly whether $(x,1) \in S$, for all the pairs $(x,1)$. If it could, it would have decided an undecidable problem, which is impossible.

$^\dagger$ This depends on $S$. If, for instance, $S$ is bounded, there might exists an algorithm that does stop.