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?
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
answered May 4, 2018 at 19:23
-
1$\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$ Commented May 28, 2018 at 16:07
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Bizarre but standing to reason! This should be the accepted answer. $\endgroup$– John L.Commented Nov 7, 2018 at 0:51
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
13
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.
-
$\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$ Commented May 7, 2018 at 7:38
-
$\begingroup$ @DavidRicherby: Where did I claim the corresponding decision problem is "Is the k'th bit of the optimum 1?"? $\endgroup$ Commented May 7, 2018 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$ Commented May 7, 2018 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$ Commented May 7, 2018 at 8:04
-
$\begingroup$ @DavidRicherby: Would appreciate it if you could take off your downvote now that your confusion is cleared up... $\endgroup$ Commented May 7, 2018 at 8:15