The Real Number Model in Numerical Analysis

In the real number model of computation one assumes that arithmetic operations with real numbers and comparisons can be done with unit cost. In numerical analysis one often deals with problems where the information is only partial. This is an essential assumption for problems defined on function spaces, such as numerical integration, zero finding, or optimization. For such problems we must usually deal with partial information consisting of function values or Fourier coefficients, because a digital computer can only handle finite sets of numbers instead of functions. In information-based complexity it is assumed that certain functionals can be evaluated by an oracle and each call of the oracle costs c, where c > 0. In this paper we describe this model of computation more carefully. We also define two variants of stochastic (or Monte Carlo) algorithms. We believe that the results of information-based complexity, see the book of Traub, Wasilkowski, and Woźniakowski (1988, "Information-Based Complexity," Academic Press, New York/London), can be reconstructed in our model with only minor changes. As an example we present a "uniform algorithm" for a "uniform problem" in numerical integration. We compare our model (in the case, where no oracle is used) with the model of Blum, Shub, and Smale (1989, Bull. Amer. Math. Soc.21, 1-46). These authors use a different cost function. Copy instructions are rather expensive in their model, while they are for free in our model. In spite of this difference we show that the sets P and NP coincide with respect to both cost functions.