Real Data—Integer Solution Problems within the Blum–Shub–Smale Computational Model

AbstractThis paper presents results connected with the theory of computation over the reals, developed recently by Blum, Shub, and Smale. The subjects of our investigation are variations of the well known Integer Linear Programming Problem and the Linear Diophantine Equation, where the coefficients are real numbers and we look for an integer solution. We show some results concerning the solvability and complexity of these problems, and we develop algorithms for their solution in the presence of additional information