https://www.dagstuhl.de/17481

### November 26 – December 1 , 2017, Dagstuhl Seminar 17481

# Reliable Computation and Complexity on the Reals

## Organizers

Norbert T. Müller (Universität Trier, DE)

Siegfried M. Rump (TU Hamburg-Harburg, DE)

Klaus Weihrauch (FernUniversität in Hagen, DE)

Martin Ziegler (KAIST – Daejeon, KR)

## For support, please contact

## Documents

Dagstuhl Report, Volume 7, Issue 11

Aims & Scope

List of Participants

Shared Documents

Dagstuhl's Impact: Documents available

Dagstuhl Seminar Wiki

(Use seminar number and access code to log in)

## Summary

The seminar was a meeting between two groups of researchers working in the related areas of reliable computing and of computational complexity on real numbers. While the first area originates in numerical analysis, the second area goes back to the roots of computer science and and computability.

Reliable computations aims to produce correct answers to numerical problems with mathematical rigor. This includes to prove that the problem is solvable and to compute mathematically correct error bounds for the solution. Reliable numerical computations solely use floating-point arithmetic to take advantage of the tremendous speed. Naturally that poses limits on the problems which can be solved, in particular the condition number. However, in contrast to purely numerical methods, no false answers are possible: Either a true error bound is computed or, a corresponding error message is given. There is a history of reliable numerical computations. In the early days, interval arithmetic was often used in a rather naive way. Still the computed results were correct, however, often wide or no bounds at all were computed. Meanwhile it is well understood how to derive effective methods for reliable numerical computations, avoiding wide bounds and pushing the set of solved problems to the limit of that of purely numerical algorithms. A number of interesting and hard mathematical problems have been solved using reliable numerical computations. This includes the famous Kepler conjecture, the existence of mutually distinct solutions to certain partial differential equations, and more. Needless to say that solving a mathematical problem requires rigorous solutions of all particular problems.

Computable analysis is a branch of computability theory studying those functions on the real numbers and related structures which can be computed by machines such as digital computers. The increasing demand for reliable software in scientific computation and engineering requires a sound and broad foundation not only of the analytical/ numerical but also of the computational aspects of real number computation. The branch of computable analysis based on the definition by Grzegorczyk and Lacombe of computable real functions (TTE, "Type 2 Theory of Effectivity") has turned out to be particularly useful for investigating computability on uncountable sets. As a central concept computability appears as a specialization of continuity. Meanwhile computability of numerous analytic problems has been investigated (from basic analysis, functional analysis, ordinary and partial differential equations, analytic functions, measure theory, dynamical systems etc.). All these examples demonstrate the usefulness of the concept.

Once a problem has been shown computable, a natural next question asks for the computational efficiency of such a solution. This is where real analysis meets (discrete) complexity theory with notions of runtime and memory/space: asymptotically with respect to n->infty for approximating the output up to absolute error 2^{-n}. The famous Bailey-Borwein-Plouffe method for instance permits to compute billions of digits of transcendental within minutes; while Bloch's constant, although proven computable, is still not known up to error 2^{-5}. In fact the distinction between polynomial and exponential time, in the discrete realm gauged for instance by complexity classes P, NP, #P, and PSPACE, re-emerges in the real case: The bit-cost of computing the maximum of an arbitrary fixed smooth (i.e. infinitely often differentiable) polynomial-time computable f : [0; 1]->[0; 1] has been shown to correspond to P-vs-NP; that of Riemann integration to #P; and that of solving an ordinary differential equation to PSPACE. On analytic functions on the other hand these operations map polynomial-time computable instances back to polynomial-time computable results.

For practical purposes and in the spirit of "algorithm engineering", the asymptotic results from complexity theory have to be refined by considering the efficiency of actual implementations. Corresponding software libraries are usually called "exact real arithmetic" (ERA) and implement real numbers in the sense of TTE. ERA implementations exist in many languages, like C, C++ JAVA, Haskell or OCaml. Internally, ERA has to perform operations on infinite data like {0,1}^omega. The user interface, however, hides the details and offers operations and functions on "exact" real numbers. In consequence, users do not need to care about aspects like rounding or truncation errors or the specification of precisions. Instead, they can concentrate on the mathematical part of the problem under consideration. As computable real functions have to be continuous, it is impossible to implement some widely used real functions (like testing on equality). In consequence, ERA cannot simply copy the double precision interface one-to-one, but needs to go its own ways. Additionally, for the reason of efficiency the representations used in TTE have to be carefully revised. The resulting speed is comparable to the use of multiple precision floating point numbers, but now without any need for manual precision control.

**Summary text license**

Creative Commons BY 3.0 Unported license

Norbert T. Müller, Siegfried M. Rump, Klaus Weihrauch, and Martin Ziegler

## Classification

- Data Structures / Algorithms / Complexity
- Semantics / Formal Methods
- Verification / Logic

## Keywords

- Computable analysis
- Reliable numerical computation
- Complexity of real computation
- Floating-point arithmetic
- Exact real arithmetic