http://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

Simone Schilke for administrative matters

Andreas Dolzmann for scientific matters

## Documents

List of Participants

Shared Documents

Dagstuhl Seminar Wiki

(Use seminar number and access code to log in)

## Motivation

The intention of this Dagstuhl Seminar is to bring together two groups of researchers working in related areas with quite orthogonal research directions: Reliable Computation and Complexity on the Reals.

Both communities are invited to exchange mutual views, challenges, and state of the art. The goal of the seminar is to unleash their full joint creativity via synergy: to foster interaction, to bridge, and to cross-promote; to tutor next generation scientists on the interface between both fields. They share, in addition to both building and being based on computer science, a solid background in mathematics and particularly advanced/hard real analysis. Moreover they have in common the emphasis on rigorous calculations with guaranteed error bounds of approximations to (not necessarily algebraic) numbers and functions.

Today numerical mathematics offers a large variety of stable and reliable algorithms. Erroneous results are very rare, rare enough not to care about that fact all the time, but yet not rare enough to ignore them. The first research direction “Reliable numerical computation” aims to produce rigorously correct answers to numerical problems. This includes to prove that the problem is solvable and to compute mathematically correct error bounds for the solution. Solely floating-point arithmetic is used to take advantage of the tremendous speed, which naturally poses limits on problems which can be solved. 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.

The second research direction “Complexity on the Reals” is a branch of computability theory studying those functions on the real numbers and related structures which can be effectively computed by machines such as digital computers. This is where real analysis meets (discrete) complexity theory with its notions of runtime and memory/space. It is a branch of TTE (“Type 2 Theory of Effectivity”), which has turned out to be particularly useful for investigating computability on uncountable sets. The success of TTE was based on the idea of joining classical computability theory from theoretical computer science with the mathematical field of topological spaces. For practical purposes and in the spirit of algorithm engineering, the asymptotic results from complexity theory are further refined by considering the efficiency of actual implementations in “exact real arithmetic”.

Most of the participants are expected to give presentations on their current research, however the schedule will ensure ample time for discussions and ad hoc sessions. We also plan to hold brainstorming sessions, to discuss unfinished ideas, to present very recent results, and to reflect the current state in general.

As the two groups of researchers currently are working quite independently, it is very hard to predict concrete results. However, we strongly anticipate that the joint meeting will be as fruitful as the join of computability theory and topology when creating TTE.

**License**

Creative Commons BY 3.0 DE

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