3
$\begingroup$

I would like to know if there are known any polynomial time algorithms for deciding the feasibility of linear programs with real (not integers) coefficients.

I know that for linear programs with integer coefficients Khachyan first proved the existence of a polynomial algorithm which can decide feasibility in polynomial time, but his method relies on the ellipsoid algorithm, which he starts with a large sphere. The radius of the sphere depends on the coefficients of the problem and also relies on the fact that they are integers. Of course, since then many other polynomial algorithms have been discovered which improved the polynomial (running time) in one way or another, but has this fundamental problem been solved?

Moreover, I see on Wikipedia that "Does LP admit a polynomial-time algorithm in the real number (unit cost) model of computation?" is an open problem. What should I understand out of it?

My understanding:

I understand the following: real coefficients need an infinite number of bits (in general) to be represented. So, "unit cost" in order to simplify that assumes that each real number is represented in "one unit", practically eliminating the memory limitation for representing the coefficients. Probably each floating point operation is also considered as a "unit" of something too ... (this is basically a BSS machine, or Real Random Access Machine ... please correct me if I am wrong)

The Khachyan's bound on the initial sphere (which initializes the ellipsoid) is based on the fact that the coefficients coding length ( $\approx$ number of bits) is finite. However, if we are now using coefficients with an "infinite" coding length, Khachyan's method is no longer applicable ... is it? This means that if the coefficients of the LP are allowed to be arbitrarily in $\mathbb{R}$ there is no known algorithm which guarantees a decision of the feasibility in a number of steps bounded above in a polynomial in the number of inequalities and space dimension, right? This means that for instance, if $\pi$ is a coefficient somewhere in LP, then there is no (known) algorithm which can solve the LP in P time, is it ?

$\endgroup$
3
  • 2
    $\begingroup$ It seems you've answered your own question, in the last paragraph of your post. I'm not sure what else there is to say. If it doesn't, perhaps you should try to formulate your question more precisely: e.g., if you aren't asking about the real number unit cost model of computation, be precise about what model of computation you have in mind; if you don't know what that model of computation is, instead do some research on that model of computation and ask about it if necessary; and so forth. $\endgroup$
    – D.W.
    Mar 7 at 20:05
  • $\begingroup$ Thank you for the comments! I have updated my question. Can you have a second look ? $\endgroup$
    – C Marius
    Mar 7 at 20:41
  • 2
    $\begingroup$ Please ask only one question per post. I count 5 questions here. "Here is everything I understand, please tell me if I got any of that wrong" is often not a good fit for our site format. Instead, I encourage you to pick one specific issue you are unsure about, and ask about that. $\endgroup$
    – D.W.
    Mar 8 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.