Consider any computational problem in which the inputs are integers. As far as I understand, if the problem has a strongly-polynomial time algorithm, it means that the algorithm uses a polynomial number of arithmetic operations in integers, and polynomial space.
Now, suppose we want to solve the same problem but the inputs are real numbers, and we have a computer that can do infinite-precision arithmetic operations on real numbers in unit cost. Can we use the same strongly-polynomial time algorithm to solve this problem in polynomial time?
What I found so far: the Wikipedia page on linear programming presents two open problems related to linear programming: "Does LP admit a strongly polynomial-time algorithm?" and "Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?" and says that they are "closely related"; my question is whether a positive answer to the first question implies a positive answer to the second question?
1 Answer 1
No. For instance, consider the following algorithm to compute the square root of the input $x$: use binary search on $t$ (computing $t^2$ in each iteration) to find the largest $t$ such that $t^2\le x$. This is a strongly polynomial time algorithm, but converting it to infinite-precision arithmetic does not give an algorithm to compute the square root on an infinite-precision input in polynomial time.