20. – 25. September 2015, Dagstuhl Seminar 15392
Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis
1 / 3 >
Auskunft zu diesem Dagstuhl Seminar erteilt
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!
Creative Commons BY 3.0 Unported license
Vasco Brattka and Akitoshi Kawamura and Alberto Marcone and Arno Pauly
- Data Structures / Algorithms / Complexity
- Verification / Logic
- Computability and complexity in analysis
- Computations on real numbers
- Descriptive complexity
- Computational complexity
- Reverse and constructive mathematics