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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.