3 ms·
An optimization problem can always be reduced to a decision problem of the form "Is X one of the optimal solutions to problem Y for input I?"
by Maxatar 2y ago
An optimization problem can always be reduced to a decision problem of the form "Is X one of the optimal solutions to problem Y for input I?"
- alex_smart 2y agoNope, the usual way of reducing optimization problem is to ask the corresponding yes/no question - for some fixed value x, is the optimal value greater than x? If you can solve the decision problem, you can solve the optimization problem by doing a binary search on the x.
- Delk 2y agoThat doesn't necessarily tell you what the solution with the optimal cost of x is, though.
- pyrale 2y agoYou can always reduce anything to anything, but in this case, the reduction is relevant because it only adds a polynomial factor. Showing that a problem can be reduced to another one in polynomial time is core to proving np-completeness. That means that tsp and tso-opt are in the same ballpark of complexity. The reason tsp-opt isn't called np-complete isn't related to its complexity, but to the fact that only decision problems get to be called that. As I said, there are problems where the decision problem and the optimization problem are completely unrelated in terms of complexity, but tsp isn't one of those.