4
$\begingroup$

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any optimization problem which is easy but its decision version is hard?

$\endgroup$
7
$\begingroup$

No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$. You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute the size of the biggest $X$) in polynomial time, you can solve the decision problem.

$\endgroup$
  • $\begingroup$ I'm thinking about the case, where we are asked to solve $max_{x \in X} f(x)$, such that $f(x)$ is a constant function but its value is hard to compute (for example, $f(x) = max_{y \in Y} g(y)$). Then any $x \in X$ is optimal, but we don't know if any $x$ makes $f(x) > k$ for a given $k$. But this is perhaps more about the definition of what it means to "solve an optimization problem"... $\endgroup$ – user2477759 May 28 '18 at 16:07
2
$\begingroup$

No, because you are supposed to choose the decision version so that any solution to the optimization problem can be used to solve the decision problem (with at most a polynomial increase in running time).

You can't choose just any unrelated decision problem; for this methodology to work, there has to be a correspondence between the optimization problem and the decision problem. The correspondence is that you need to make sure that any algorithm A for the optimization problem can be used to solve the decision problem, with at most polynomially many invocations of A.

$\endgroup$
2
$\begingroup$

Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the $x$ that maximizes $f(x)$", then consider the function $f(x) = \max_{y\in Y}g(y)$ such that $\max_{y\in Y}g(y)$ is hard to compute. The optimization problem is easy to solve since $f(x)$ is constant w.r.t. $x$, but the decision problem — decide whether there exists an $x$ such that $f(x)>k$ — is hard to solve.

$\endgroup$
  • $\begingroup$ Bizarre but standing to reason! This should be the accepted answer. $\endgroup$ – Apass.Jack Nov 7 '18 at 0:51
0
$\begingroup$

No... if the optimal solution is $1101$ in binary, then that inherently already represents the solution to the four corresponding decision problems.

So if finding $1101$ is easy, that means computing the respective $1$, $1$, $0$, and $1$ was easy too.

$\endgroup$
  • $\begingroup$ The decision version of an optimisation problem is “Is the optimum at least/most $x$?” not “Is the $k$th bit of the optimum $1$?” The latter can be a much easier problem, especially given that “Is the last bit of the optimum $1$?” Is equivalent to “Is the optimum an odd number?” $\endgroup$ – David Richerby May 7 '18 at 7:38
  • $\begingroup$ @DavidRicherby: Where did I claim the corresponding decision problem is "Is the k'th bit of the optimum 1?"? $\endgroup$ – Mehrdad May 7 '18 at 7:57
  • $\begingroup$ Your second paragraph talks about computing individual bits of the optimum. That doesn’t seem relevant unless “the decision problem” is to compute one of those bits. $\endgroup$ – David Richerby May 7 '18 at 8:01
  • $\begingroup$ @DavidRicherby: Sure it does? First question could be "is the optimum at least 1000 [yes]", second one "is the optimum at least 1100 [yes]", third one "is the optimum at least 1110 [no]", fourth one "is the optimum at least 1101 [yes]". $\endgroup$ – Mehrdad May 7 '18 at 8:04
  • $\begingroup$ @DavidRicherby: Would appreciate it if you could take off your downvote now that your confusion is cleared up... $\endgroup$ – Mehrdad May 7 '18 at 8:15

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.