On the complexity of linear programming in the BSS-model

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., g iven A is an element of R-mxn,b is an element of R-m, does there exist a is an element of R+n s.t. A x x = b?) is reducible in polynomial time to (F-2 ,F-zero,+(2)) (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,LP ,,,) is polynomially equivalent to the more special decision problem (F2+,F -zero,+(2+),) (i.e., given a polynomial f is an element of F-2 with f(x)gre ater than or equal to 0 for all x is an element of R-n, does there exist a nonnegative real zero?). (C) 1999 Elsevier Science B.V. All rights reserved .