2 MARTIJN BAARTSE AND KLAUS MEER reflecting the underlying structure are of major interest. One then disregards the influence of round-off errors and uses an idealized model that computes with real or complex numbers as entities. This allows to focus on algebraic properties of problems and algorithms solving them. One of the first formalizations of such a viewpoint in complexity theory has been worked with in the area of Algebraic Complexity Theory [25] and can be traced back at least to the 1950’s. Models of computation used there are algebraic circuits and straight line programs. In 1989, Blum, Shub and Smale introduced a model of computation now called the BSS model, see [18, 19]. It gives a general approach to computability over rings and fields with a particular emphasis on R and C. When considered over the finite field Z2 it results in the classical Turing machine model, whereas over fields like the real or complex numbers it gives a uniform model generalizing the ones previously used in algebraic complexity theory. Let us mention that different models of computation have become more and more interesting in recent years both in computer science and mathematics. Think about such diverse models as Neural Networks [48], Quantum Computers [81], Analog Computers [101], Biological Computers [43] to mention a few. Beside in algebraic complexity the BSS model is also used as underlying computational model in the area of Information Based Complexity in which algorithms for numer- ical problems without complete information are studied [82, 108]. Computational models dealing with real numbers are also studied in Recursive Analysis. Here, objects like real numbers or real functions are coded in a certain way by Cauchy sequences leading to notions like that of a computable real (already introduced by Turing) and computable real number functions. The theory arising from this ap- proach is focussing more on stability of real number algorithms and thus different from the setting of this paper. For introduction and some additional controversial discussions on the question which model to use in what situation we refer the reader to the following literature: [16,22,53,96,107,108]. In this paper the Blum-Shub-Smale model builds the main topic of interest. The intention is to give an introduction into problems and methods relevant in real number complexity theory. The paper is organized as follows. Section 2 starts with a motivating example from kinematics that leads to several interesting questions in complexity, both with respect to the classical Turing and the real/complex number model. These problems are outlined and lead to a formal introduction of the real number model in the following section. There, basic complexity classes as well as the concept of NPR-completeness are introduced and some first results are presented. We then focus on structural complexity theory for the real and complex numbers by discussing three different topics: Transfer results between different computational models, analysis of the structure inside NPR and NPC along the lines of a classical result by Ladner in the Turing model, and recursion theory over the reals. The rest of the paper then focusses on Probabilistically Checkable Proofs PCPs. The PCP theorem by Arora et al. [2, 3] was a cornerstone in Theoretical Computer Science giving a new surprising characterization of complexity class NP and having tremendous applications in the area of approximation algorithms. After introducing the main ideas behind probabilistically checkable proofs we give a detailed proof of the existence of long transparent proofs for NPR and NPC. Then, we outline how one can obtain a real analogue of the PCP theorem along the lines of a more recent proof of the classical PCP theorem by Dinur [38].
Previous Page Next Page