1
$\begingroup$

If a decision problem is in P, is the associated optimization problem then also efficiently solvable?

I always thought that this is the case but according to Wikipedia page on Decision Problems the complexity of a decision and function problem might differ and to me a function problem was always a special case of an optimization problem, hence I was under the impression that if the decision problem is efficiently decidable the same applies to the corresponding optimization problem.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Given a decision problem, how is the associated optimization problem defined? To be clear: I know how to define a decision problem from an optimization problem, I am asking for the converse. $\endgroup$ – Steven Jan 13 at 16:55
  • $\begingroup$ @Steven I not aware of a general transformation from a decision to an optimization problem. And yes, you are right, different transformations will lead to different results. But I'm thinking of optimization problems that could be answered by using the decision algorithm as an oracle. E.g. "is this the shortest path?", then in theory every (finite) path could be tested. In this particular case, the question boils down to the question if the number of paths is polynomially bounded. $\endgroup$ – Nepomuk Hirsch Jan 13 at 17:13
  • $\begingroup$ @Inuyashayagami I'm refering to definitions given on this Wikipedia page: en.wikipedia.org/wiki/Decision_problem $\endgroup$ – Nepomuk Hirsch Jan 13 at 17:15
2
$\begingroup$

Let us consider a generic optimization problem:

Maximize $f(x)$ subject to the constraint $x \in \mathcal{D}$.

The corresponding decision version is

Given $\mathcal{D}$ and $T$, is there $x \in \mathcal{D}$ such that $f(x) \geq T$?

In most cases, the range of $f(x)$ is at most exponential in the description length of $\mathcal{D}$, and so the optimization problem reduces to the decision version via binary search. For example, if $0 \leq f(x) \leq n$, then we first ask whether there is a solution with $f(x) \geq n/2$; depending on the answer, we ask whether there is a solution with $f(x) \geq n/4$ (if the answer was negative) or with $f(x) \geq 3n/4$ (if the answer was positive); and so on.

Conversely, if we can solve the optimization problem then we can easily answer the decision problem, and so the two are essentially equivalent.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I understand that in many cases the opt version can be solved via the decision version. But you also write "in most cases". Does this mean that there are counterexamples? Do you have an example? Or is it possible in ALL cases? $\endgroup$ – Nepomuk Hirsch Jan 23 at 20:53
  • $\begingroup$ You can probably cook up a weird example. $\endgroup$ – Yuval Filmus Jan 23 at 20:55
  • $\begingroup$ Ok understood. According to the paper @vonbrand mentioned, it seems such examples exist. $\endgroup$ – Nepomuk Hirsch Jan 23 at 21:05
1
$\begingroup$

Take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search SIAM J. on Computing 23:1 (feb 1994), a version for class use is here. Short answer: If the decision problem is in NP, they are "equivalent" (the optimization problem can be solved using a polynomial number of calls to the decision problem), if the decision problem is harder (and some quite plausible conjectures pan out) they aren't.

Improve this answer
$\endgroup$
2
  • $\begingroup$ In the intro of this paper it says: "...to indicate that proving membership may be harder than deciding it". Doesn't this contradicts your answer? $\endgroup$ – Nepomuk Hirsch Jan 23 at 21:01
  • $\begingroup$ @NepomukHirsch, "if the decision problem is in NP, ...". The paper concludes that if it isn't, the decision and search problem can be wildly different in complexity. $\endgroup$ – vonbrand Feb 5 at 21:09
0
$\begingroup$

Consider the Travelling Salesman Problem (TSP).

Decision Version (DV): Given an undirected weighted graph $G$, does there exist a Hamiltonian cycle of weight at most 'w' in the Graph?

Optimization Version (OV): Given an undirected weighted graph $G$, find the hamiltonian cycle of minimum weight?

Case 1: If P $=$ NP.

Since there is a polynomial-time reduction from DV to OV and vice-versa (link), both the problems are in P. Here, the complexity of both the problems are the same.

Case 2: If P $\neq$ NP

Here, we will show that the complexity of both the problems are different.

Note that the Decision version of TSP is in NP since given a sequence of vertices, we can verify in polynomial time if the sequence is a hamiltonian cycle of weight at most 'w'.

However, for the Optimization version of TSP, how will you know if it belongs to NP. In other words, given a Hamiltonian cycle of 'w', how can you verify if it is the optimal one? As per my thinking, to verify its optimality you must know the optimal solution. Since P $\neq$ NP, we can not find the optimal solution in polynomial time. Therefore, we might not be able to say if TSP is in NP.

Thus, the complexity of Decision Version and Optimization Version could be different.

Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Wouldn't the decision version be: "Given an undirected weighted graph $G$ and $w$, is there an Hamiltonian cycle of weight at most $w$ in the Graph?". In this case if the decision version can be solved in polynomial time, then the optimization version can be solved in poly-time as well. There: maximum value of $w$ is upper bounded by $nW$ where $W$ is the maximum weight of an edge. The size of the instance is at least $n+\log W$. A poly-time algorithm for the optimization problem just runs a binary search using the decision problem to find the minimum weight $W^*$. $\endgroup$ – Steven Jan 13 at 17:38
  • $\begingroup$ Many thanks! I have edited the answer. $\endgroup$ – Inuyasha Yagami Jan 13 at 17:42
  • $\begingroup$ This requires time $O(\log nW) = O(\mbox{poly}(n+\log W))$. Using some tricks on the edge weights, this also yields the optimal solution: just append a $O(n^2)$-bit binary string to the binary representation of the weight of each edge in $G$, so that each edge has a distinct bit set to $1$ in this string. Then the least significant bits of $W^*$ will be the characteristic vector of the set of edges in the cycle. $\endgroup$ – Steven Jan 13 at 17:42
  • $\begingroup$ In the earlier case, the problem should come while doing a reduction from decision version to optimization version right? not the other way around since we can also apply binary search if the decision version ask for weight 'w' cycle only $\endgroup$ – Inuyasha Yagami Jan 13 at 17:45
  • $\begingroup$ Anyway, I'd agree there can be cases where the decision problem is decidable in poly-time (and is hence in P) but the optimization problem is not solvable in poly-time. Hence, the answer to my initial question is: "No, even if a decision problem is in P, the associated optimization problem might not be solvable in poly-time. But: the decision problem is a lower bound for the complexity of the optimization problem". Would you agree? $\endgroup$ – Nepomuk Hirsch Jan 13 at 17:51

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.