A survey on real structural complexity theory (Q1280231)

\textit{L. Blum, M. Shub} and \textit{S. Smale} [(*) Bull. Am. Math. Soc., New Ser. 21, 1-46 (1989; Zbl 0681.03020)] introduced an analog to the Turing machine for computing over arbitrary (ordered) rings. It allows studying complexity issues outside the discrete world and ties these closer to classical mathematics than the more logical approach. The paper overviews research done since then on the BSS-model, mostly for the case that the ring is \(\mathbb R,\) the real numbers or another continuous domain. This specialization -- already in BSS in a prominent position -- is important, e.g. in numerical analysis where the bit-size of reals does not enter the considerations. Section 2 provides a non-graphic definition of the BSS-machine in the real setting. It allows the four elementary arithmetic operations, branching on inequalities, and copying. Associated important concepts like halting-set, and decision problem -- familiar from the Turing setting -- are explained. The important difference is the idealized entity the BSS-machine deals with -- any real number independent of its magnitude - and the idealized cost measure: any basic operation has cost unit one. The analogues and refinements to the NP-completeness of the 4-feasability problem established in (*) are surveyed; and the close connection of the decidability of \(\text{NP}_{\mathbb R}\)-problems with quantifier elimination is mentioned. Section 3 focuses on results concerning the weak BSS model of \textit{P. Koiran} [J. Comput. Syst. Sci. 54, 177-189 (1997; Zbl 0869.68049)]. In it more realistic cost measures for the BSS-model are considered. Classical complexity classes are obtained as the boolean parts of real-number complexity classes, see also \textit{J. B. Goode} [J. Symb. Log. 59, No. 1, 92-105 (1994; Zbl 0804.03028)] (in spite of its somewhat condescending review). Surveyed is a host of further results obtained by modifications of the BSS-m by restricting the basic operations to linear ones or even only additive ones, and by restricting the test questions allowed to pure equality tests. Section 4 points to results concerning analogues of the famous \(P\neq \text{NP}\) conjecture for various (e.g. weak, linear, additive, full, complex-number \dots) versions of the BSS-model. Section 5 reviews the foundations of Recursion Theory for the reals. It indicates papers that prove refinements and modifications of the BSS-theorem that halting sets over \(\mathbb R\) are countable unions of basic semialgebraic sets. The close links with undecidable subsets of \(\mathbb R\) and analogs to Gödel's incompleteness theorem are emphasized. Section 6 surveys results as in Section 4 but now stressing the change of the field or more generally the change to other structures (sets with operations). Section 7: One way to relate model theory to complexity is upon considering the logical complexity of defining a property. This combines computational complexity with logical definability and leads to a machine independent model-theoretic approach to describe real complexity classed. \(\text{NP}_{\mathbb R}-\)completeness of the 4-feasability problem turns then out as a special case of a theorem obtained by \textit{E. Grädel} and \textit{K. Meer} [Descriptive complexity theory over the real numbers, Lect. Appl. Math. 32, 381-403 (1996; Zbl 0861.03034)]. Section 8 mentions research done on probabilistic BSS-machines and on incorporating in the BSS-model also problems of numerical analysis like round-off errors. To sum up, the paper guides to the contents of some 130 papers, most of which influenced by or of relevance to the computational model of Blum, Shub, and Smale. No proofs are provided but many definitions and theorems are given in their precise form and put in their proper context.