3
$\begingroup$

Suppose that we have an optimization problem defined as follows:

$OPT$ = Given an input string defining a set of feasible solutions $F$ and an objective function $f$, find $x\in F$ maximizing $f(x)$

and the equivallent decision problem

$L_{OPT}$ = Given an input string defining $F$ and $f$ and a target value $u\in Q$, decide if there is a solution $x \in F$ so that $f(x) \geq u$

Assuming that an efficient solution here is defined as an algorithm that runs in polynomial time in the length of the input, then if we have an efficient solution for $OPT$ it is trivial to see that we can get an efficient solution for $L_{OPT}$. However, my teacher said that we could have that $L_{OPT}$ has an efficient solution without $OPT$ having an efficient solution.

How is the latter possible? If we can efficiently solve $L_{OPT}$, wouldn't we be able to run a binary search algorithm to find the solution for $OPT$?

$\endgroup$
  • 2
    $\begingroup$ I would say so, and I think that if you understood correctly what your teacher said he/she is wrong. $\endgroup$ – Albert Hendriks Jun 9 '15 at 15:29
  • 1
    $\begingroup$ I think some of our reference questions discuss this. (I think you are right, too.) $\endgroup$ – Raphael Jun 9 '15 at 17:59
  • $\begingroup$ If you drop the polytime assumption then your teacher is right: consider Diophantine equations with large solutions, that may still be easy to decide. $\endgroup$ – András Salamon Aug 15 '15 at 17:22
1
$\begingroup$

If the objective function $f$ is easy to compute, you can use a solution to $OPT$ to solve $L_{OPT}$: find some $x$ which maximises the objective function; compute $f(x)$ and output "yes" if it meets or exceeds the threshold $u$ (output "no" otherwise).

That is, $L_{OPT}$ reduces to $OPT$ (for some suitable definition of the reduction type), and is in this sense easier.

If we let $OPTVAL$ be the function problem of computing the optimal value, but not the solution which has this value, $OPTVAL$ reduces to $L_{OPT}$ via binary search. (Also $OPTVAL$ reduces to $OPT$: compute the optimal solution, then compute its value.)

Note that the reduction in one direction is a member of a smaller class of reductions than in the other: when solving $L_{OPT}$ via $OPT$ you have the reduction $r$ and some post-processing $p$ such that for every instance $i$, the answer to $L_{OPT}$ equals the output of $p(OPT(r(i))$. That is, it's a one-call reduction (but not tail call, which it can't be due to a type mismatch). The reduction from $L_{OPT}$ to $OPTVAL$ is a multi-call reduction (with binary search it will make a logarithmic number of queries).

It's not clear to me that you can reduce $OPT$ to $OPTVAL$, not even with multiple calls: given an oracle which tells you what the optimal value is, how to you compute a solution with that value, generically?

However, most "natural" problems will probably let you do this. For instance, if we represent a graph $G$ as the number of vertices followed by an enumeration of the complement of the edge set and want to compute the chromatic number (smallest $k$ such that the graph is $k$-colourable), we can let $G'$ be $G$ with an edge added and ask our $OPTVAL$-oracle what the optimal value is. Whenever such a change doesn't increase the number of colours required, we learn of an additional constraint we can impose. Do so until it's no longer possible (at most polynomially often); now each vertex is adjacent to every vertex of any different colour, i.e. $u$ and $v$ have the same colour for every $(u, v) \in (V \times V) \setminus E$. Assign a colour to an uncoloured vertex, apply this rule and repeat until the graph is $k$-coloured.

One could generalise this: let solution-extractable optimisation problems be those such that with oracle access to the optimal value on smaller instances and the given instance, you can compute the optimal solution. Then you can multi-call reduce $OPT$ to $OPTVAL$ on solution-extractable problems (by construction). Of course, you can also compute optimal solutions to the smaller instances, since they are instances of a solution-extractable problem by assumption; maybe that helps to extract the optimal solution to the bigger instance.

It would be nice to have some generic constructions that enable this. Here's one idea:

Given some optimisation problem $P$ with a bound $k$ on the solution length, let instances of $Q$ be triples $(x, 1^{2k-l}, p)$ where $x$ are $P$-instances and $p$ has length $l$ be the problem of finding optimal solutions to $P$ which have $p$ as a prefix. If you can solve $OPTVAL_Q$ then $P$ is solution-extractable: whenever $OPTVAL$ of $Q$ goes down both when you extend $p$ with a $0$ and when you extend it with a $1$, $p$ is a longest optimal solution; otherwise, extend $p$ with any value which doesn't decrease the objective function. Note that padding the problem with a number of ones equal to two times the bound on the solution length, we make the self-reductions downward when extending $p$.

Probably bit-by-bit solution extraction can be extended to chunk-by-chunk extraction if chunks have length at most $O(\log n)$ (since there's only polynomially many values to try out).

$\endgroup$
  • $\begingroup$ cs.umd.edu/~samir/grant/self.pdf gives a definition of self-reducibility which might or might not capture my intuition. It may be worth studying for anyone interested in pursuing this further. (Its main result is that planar 4-colorability is not self-reducible, which I find quite interesting.) $\endgroup$ – Jonas Kölker Mar 21 '17 at 15:36
0
$\begingroup$

There is some degree of truth in it: For the decision problem, you need to either prove that a solution exists (often by finding one), or prove that none exists. If the target value is far away from the optimal value, then it may be easy to either find a solution or prove that non exists; the closer you choose a target value to the optimal value, the harder you can expect it to be.

You may have situations where you are never asked to solve an instance of the decision problem that is hard. For the optimisation problem, you must solve all problems, including the hard ones. For example, it will be trival to find a tour connecting all 48 continental capitols of the USA with a tour of less than 20,000 miles, and trivial to prove that a tour of 1,000 miles is not possible. But finding the shortest possible tour will be hard.

$\endgroup$

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.