From Bernhard Korte, Jens Vygen, Combinatorial Optimization,

Instances of LINEAR PROGRAMMING are vectors and matrices. Since no strongly polynomial-time algorithm for LINEAR PROGRAMMING is known we have to restrict attention to rational instances when analyzing the running time of algorithms.

I was wondering why does the absence of strongly polynomial time algorithms for linear programming imply restriction to rational instances?

  • $\begingroup$ It may be because time complexity analysis on real numbers is a lot harder to define? Restricting to finite-size objects like rational is one way to talk about complexity. $\endgroup$
    – jmad
    Commented Dec 17, 2012 at 19:34

1 Answer 1


A strongly polynomial algorithm in the context of linear programming probably means an algorithm in the arithmetic model (where numbers can be added, multiplied, compared and so on), whose running time does not depend on the magnitudes of the numbers involved. Such an algorithm could be applied directly for real numbers. Examples of algorithms of this type are the simplex algorithm and the criss-cross algorithm, both really a collection of related algorithms. However, variants of these algorithm are either known not to be polynomial-time, or (in some cases) not known and not expected to be polynomial-time.

Other algorithms for linear programming exist: the ellipsoid algorithm and the interior-point algorithm (again, there are really many variants of these algorithms). The number of iterations in each case depends on the precision needed to guarantee reaching an optimal solution, and that's why they are not strongly polynomial. While these algorithms can also be implemented in the arithmetic model, convergence is no longer guaranteed to take polynomial time.

When the inputs are rational numbers, then the number of iterations needed to converge is polynomial in the length of the input, and therefore these algorithms become 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.