Blum–Shub–Smale machine

Definition

A BSS machine M is given by a list I of N+1 instructions (to be described below), indexed 0, 1, \dots, N. A configuration of M is a tuple (k,r,w,x), where k is the index of the instruction to be executed next, r and w are registers holding non-negative integers, and x=(x_0,x_1,\ldots) is a list of real numbers, with all but finitely many being zero. The list x is thought of as holding the contents of all registers of M. The computation begins with configuration (0,0,0,x) and ends whenever k=N; the final content of x is said to be the output of the machine.

The instructions of M can be of the following types:

• Computation: a substitution x_{0} := g_{k}(x) is performed, where g_{k} is an arbitrary rational function (a quotient of two polynomial functions with arbitrary real coefficients); registers r and w may be changed, either by r := 0 or r := r + 1 and similarly for w. The next instruction is k+1.
• Branch(l): if x_0 \geq 0 then goto l; else goto k+1.
• Copy(x_r, x_w): the content of the "read" register x_r is copied into the "written" register x_w; the next instruction is k+1.

Theory

Blum, Shub and Smale defined the complexity classes P (polynomial time) and NP (nondeterministic polynomial time) in the BSS model. Here NP is defined by adding an existentially-quantified input to a problem. They give a problem which is NP-complete for the class NP so defined: existence of roots of quartic polynomials. This is an analogue of the Cook-Levin Theorem for real numbers.

References

References

1. (1989). "On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, Recursive Functions and Universal Machines". Bulletin of the American Mathematical Society.
2. Minsky, Marvin. (1967). "Computation: Finite and Infinite Machines". Prentice–Hall, Inc..