On the Complexity of Linear Programming in the BSS-model Original Research Article

We consider the Blum–Shub–Smale model of computation over the reals. It was shown that the Linear Programming Feasibility problem (LP,LPyes) (i.e., given A∈Rm×n,b∈Rm, does there exist an x∈R+n s.t. A×x=b?) is reducible in polynomial time to (F2,F2zero,+) (i.e., given a polynomial f with real coefficients and degree at most 2, does there exist a nonnegative real zero?). We show that (LP,LPyes) is polynomially equivalent to the more special decision problem (F2+,Fzero,+2+) (i.e., given a polynomial f∈F2 with f(x)⩾0 for all x∈Rn, does there exist a nonnegative real zero?).