How do you handle numerical issues when converting optimization problems to decision problems?

Question

The trick of converting an optimization problem to a decision problem is well-known - you add a real number input to the decision problem for thresholding.

For example, this is taken from Wikipedia about the traveling salesman problem:

"The problem has been shown to be NP-hard (more precisely, it is complete for the complexity class FPNP; see function problem), and the decision problem version ("given the costs and a number x, decide whether there is a round-trip route cheaper than x") is NP-complete."

However, it is not clear to me how we actually tackle numerical issues with this kind of thresholding. For example, how can we assure, given our finite accuracy in the algorithm, that we are not away from x slightly? More specifically, if we set x=1.0, and we managed to show using our finite accuracy that it holds for 0.9999.., how can we tell it is not actually holding for x=1.0? (0.99999... is a representation of 1 as well.)

This problem does not happen when x is an integer value.

I would appreciate any response. Of course, there are many algorithms that assume that we have "access" to a Turing machine that can compute any real number... But I find this case especially important to distinguish from the other cases, because it could affect the complexity of the algorithm, and our whole point is to show hardness of some sort. So, I don't think we can just avoid this issue by just making the assumption that we have such a powerful Turing machine.

Answer 1

For most NP-complete problems, you can without loss of generality work with rational numbers, in which case you don't run into issues of precision. There are a few problems which do run into difficulties of precision; e.g., geometry problems where you have to compare sums of square roots. One famous example is the minimum length triangulation problem: given a set of points in the plane, what is the length of the minimum length of a triangulation of these points? Since nobody knows how to efficiently tell whether a sum of square roots is larger or smaller than a given number, it's not even clear that you can find a witness showing that a set of points has a triangulation smaller than some integer $k$. However, it's still possible to show that this problem is NP-hard. You just have to use instances in your reduction which are constructed so this precision issue doesn't occur. The precision issues, however, have so far prevented anyone from showing the decision problem is in NP.