A note on a theorem of Blum, Shub, and Smale

AbstractRecently, Blum, Shub, and Smale (1988) introduced a new model for computations over the real numbers. They define the notion of “NP-completeness over R” and prove an analog of Cook's Theorem in the classical theory of NP-completeness: The 4-Feasibility-Problem, i.e., the problem of deciding whether a real polynomial ƒ: Rn → R of degree 4 has a zero or not, is NP-complete over R. In this note we show the polynomial-time solvability of the k-Feasibility-Problem for k ⩽ 3