Erich Novak: The real number model in numerical analysis

A paper with this title appeared in the J. of Complexity, 11 (1995), 57-73.

Abstract

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 Wozniakowski (1988), 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). 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.

Some references to related work

L. Blum, M. Shub, and S. Smale
On a theory of computation and complexity over the real numbers:
NP completeness, recursive functions and universal machines.
Bull. of the AMS 21 (1989), 1-46.

K. Meer and C. Michaux
A survey on structural real complexity theory
Bull. of the Belgian Math. Soc. Simon Stevin, 4 (1997), 113-148.

E. Novak and H. Wozniakowski:
Topological complexity of zero finding.
J. Complexity 12 (1996), 380-400.

L. Plaskota
Noisy Information and Computational Complexity
Cambridge University Press, 1996

J. Renegar, M. Shub, S. Smale (eds.)
The mathematics of numerical analysis
1995 AMS-SIAM Summer Seminar, Park City, Utah
Lectures in applied mathematics, AMS, 1996

S. Smale
Some remarks on the foundations of numerical analysis
SIAM Rev., 32 (1990), pp. 211-220

S. Smale
Complexity theory and numerical analysis
To appear in Acta Numerica

J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski
Information-Based Complexity
Academic Press, Boston, 1988