http://www.dagstuhl.de/15392

September 20 – 25 , 2015, Dagstuhl Seminar 15392

Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis

Organizers

Vasco Brattka (Universität der Bundeswehr – München, DE)
Akitoshi Kawamura (University of Tokyo, JP)
Alberto Marcone (University of Udine, IT)
Arno Pauly (University of Cambridge, GB)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 5, Issue 9 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
Dagstuhl's Impact: Documents available

Summary

Reducibilities such as many-one, Turing or polynomial-time reducibility have been an extraordinarily important tool in theoretical computer science from its very beginning. In recent years these reducibilites have been transferred to the continuous setting, where they allow to classify computational problems on real numbers and other (continuous) data types.

On the one hand, Klaus Weihrauch's school of computable analysis and several further researchers have studied a concept of reducibility that can be seen as an analogue of many-one reducibility for functions on such data. The resulting structure is a lattice that yields a refinement of the Borel hierarchy and embeds the Medvedev lattice. Theorems of for-all-exists form can be easily classified in this structure.

On the other hand, Stephen Cook and Akitoshi Kawamura have independently introduced a polynomial-time analogue of Weihrauch's reducibility, which has been used to classify the computational complexity of problems on real numbers and other objects. The resulting theory can be seen as a uniform version of the complexity theory on real numbers as developed by Ker-I Ko and Harvey Friedman.

The classification results obtained with Weihrauch reducibility are in striking correspondence to results in reverse mathematics. This field was initiated by Harvey Friedman and Stephen Simpson and its goal is to study which comprehension axioms are needed in order to prove certain theorems in second-order arithmetic. The results obtained so far indicate that Weihrauch reducibility leads to a finer uniform structure that is yet in basic agreement with the non-uniform results of reverse mathematics, despite some subtle differences.

Likewise one could expect relations between weak complexity theoretic versions of arithmetic as studied by Fernando Ferreira et al., on the one hand, and the polynomial-analogue of Weihrauch reducibility studied by Cook, Kawamura et al., on the other hand.

While the close relations between all these approaches are obvious, the exact situation has not yet been fully understood. One goal of our seminar was to bring researchers from the respective communities together in order to discuss the relations between these research topics and to create a common forum for future interactions.

We believe that this seminar has worked extraordinarily well. We had an inspiring meeting with many excellent presentations of hot new results and innovative work in progress, centred around the core topic of our seminar. In an Open Problem Session many challenging current research questions have been addressed and several of them have been solved either during the seminar or soon afterwards, which underlines the unusually productive atmosphere of this meeting.

A bibliography that we have compiled during the seminar witnesses the substantial amount of research that has already been completed on this hot new research topic up to today.

This report includes abstracts of many talks that were presented during the seminar, it includes a list of some of the open problems that were discussed, as well as the bibliography.

Altogether, this report reflects the extraordinary success of our seminar and we would like to use this opportunity to thank all participants for their valuable contributions and the Dagstuhl staff for their excellent support!

License
  Creative Commons BY 3.0 Unported license
  Vasco Brattka, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity
  • Verification / Logic

Keywords

  • Computability and complexity in analysis
  • Computations on real numbers
  • Reducibilities
  • Descriptive complexity
  • Computational complexity
  • Reverse and constructive mathematics

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support