Computability and Complexity in Analysis

Summary

The seminar “Computability and Complexity in Analysis” was held in Dagstuhl from April 21 to 25, 1997. It was attended by 43 computer scientists, mathematicians and logicians who are interested in the diverse areas of computational analysis. The 33 talks presented here represented many different theories and approaches in this topic.

In the foundational study, they included constructive analysis (of E. Bishop), recursive analysis, type-2 theory of effectivity and the domaintheoretic approach. Classical theories on real-valued functions have been extended to more general functional spaces. Specific problems in computable analysis, such as the Riemann mapping theorem and problems in calculus of variations, have also been presented. In the complexity study, a number of talks were about the modifications and comparisons of three different models: Turing machine-based complexity theory, information-based complexity theory (IBC) and real RAM-based complexity theory (BSS). More practical issues, including interval analysis, automatic result verification, bounded-value problem, on-line computation and geometric and stochastic modelling, were also presented.