Algebraic calculation models

In theoretical computer science , especially in complexity theory , algebraic calculation models are those attempts to formally grasp the concept of the calculable, which assume that exact operations can be carried out on real or complex numbers . Due to this demanding requirement, it is a matter of purely abstract calculation models, without any possibilities for a physical realization.

Analogous to the theory of automata that operate on discrete structures, very similar questions arise based on the algebraic models:

• Are there undecidable problems in algebraic calculation models ? (Yes)
• How do the complexity classes of the P, NP and NP-complete problems (etc.) explained in the same way look like in this calculation model? (These three classes can each be explained meaningfully, but they do not coincide with the discrete classes. The analogous P-NP problem is currently also open for algebraic calculation models)
• What structure do decidable problems have? (Leads to the concept of semi-algebraic sets) ${\displaystyle \mathbb {R} }$

BSS machines

A canonical approach to approach algebraic calculation models are the Blum - Shub - Smale machines (BSS machines) named after their description . A machine of this class is defined to allow exactly the following operations:

• The arithmetic operations between two registers on the underlying structure: +, -, ×, ÷.
• Assignment of one of a finite number of constants.
• Copy commands for two fixed registers.
• Compare with the zero, ie "= 0" above and " " above . ${\displaystyle \mathbb {C} }$ ${\displaystyle \geq 0}$ ${\displaystyle \mathbb {R} }$
• A stop order.

A BSS machine can then be specified by an ordered set of instructions of this type, as well as a finite number of given constants. In the semantics of such a machine, the instructions are executed one after the other, unless the stop command is present - in which case the calculation is canceled - or a comparison condition is met. In this case you jump to a command with the corresponding number, which is specified in the comparison command.

There are other attempts to explain algebraic calculation models that, for example, also allow the root function or trigonometric operations and lead to different results than the complexity theory for BSS machines.

literature

• Lenore Blum, Felipe Cucker, Michael Shub, Steve Smale: Complexity and Real Computation , 1998 edition. Edition, Springer, New York October 30, 1997, ISBN 978-0-387-98281-6 .

• Saugata Basu, Richard Pollack, Marie-Françoise Coste-Roy: Algorithms in Real Algebraic Geometry , 2nd edition. Edition, Springer, Berlin; New York August 21, 2006, ISBN 978-3-540-33098-1 .

• Peter Bürgisser, Michael Clausen, Amin Shokrollahi, T. Licktig: Algebraic Complexity Theory , 1997 edition. Edition, Springer, Berlin; New York December 16, 1996, ISBN 978-3-540-60582-9 .

Individual evidence

1. ↑ Lenore Blum, Mike Shub, Steve Smale, others: On a theory of computation and complexity over the real numbers: $ NP $ -completeness, recursive functions and universal machines . In: Bulletin (New Series) of the American Mathematical Society . 21, No. 1, 1989, pp. 1-46.