Dagstuhl Seminar 15392
Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis
( Sep 20 – Sep 25, 2015 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/15392
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)
Contact
- Andreas Dolzmann (for scientific matters)
- Annette Beyer (for administrative matters)
Impacts
- Dividing by Zero - How Bad Is It, Really? : article in 41st International Symposium on Mathematical Foundations of Computer Science : pp. 1-14 - Kihara, Takayuki; Pauly, Arno - Wadern : LZI, 2016 - (Leibniz International Proceedings in Informatics ; 58 : article).
- Reverse Mathematics of Matroids : article in LNCS 10010: Computability and Complexity : pp. 143-159 - Hirst, Jeffry L.; Mummert, Carl - Berlin : Springer, 2017 - (Lecture notes in computer science ; 10010 : article).
- The proof-theoretic strength of Ramsey's theorem for pairs and two colors : article - Patey, Ludovic; Yokoyama, Keita - Amsterdam : Elsevier, 2018. - pp. 1034-1070 - (Advances in Mathematics ; 330. 2018 : article).
- Using Ramsey's Theorem Once - Hirst, Jeffry L.; Mummert, Carl - Cornell University : arXiv.org, 2016. - 10 pp..
Reducibilities such as many-one, Turing or polynomial-time reducibility have been an extraor- dinarily 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 classifed 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 withWeihrauch 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 thatWeihrauch 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 the proposed seminar is 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.
- Computability and complexity in analysis
- Reverse mathematics
- Uniform reducibilities
- Weak subsystems of arithmetic
The seminar is scheduled to be held in parallel to the Dagstuhl Seminar 15391 Algorithms and Complexity for Continuous Problems. We are planning to explore possible subjects of mutual interest.
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, Akitoshi Kawamura, Alberto Marcone, and Arno Pauly
- Vasco Brattka (Universität der Bundeswehr - München, DE) [dblp]
- Matthew de Brecht (NICT - Osaka, JP) [dblp]
- Damir D. Dzhafarov (University of Connecticut - Storrs, US) [dblp]
- Fernando Ferreira (University of Lisboa, PT) [dblp]
- Willem L. Fouché (UNISA - Pretoria, ZA) [dblp]
- Cameron Freer (MIT - Cambridge, US) [dblp]
- Guido Gherardi (Universität der Bundeswehr - München, DE) [dblp]
- Peter Hertling (Universität der Bundeswehr - München, DE) [dblp]
- Denis R. Hirschfeldt (University of Chicago, US) [dblp]
- Jeffry L. Hirst (Appalachian State University - Boone, US) [dblp]
- Rupert Hölzl (Universität Heidelberg, DE) [dblp]
- Hajime Ishihara (JAIST - Ishikawa, JP) [dblp]
- Akitoshi Kawamura (University of Tokyo, JP) [dblp]
- Takayuki Kihara (University of California - Berkeley, US) [dblp]
- Ulrich Kohlenbach (TU Darmstadt, DE) [dblp]
- Alexander P. Kreuzer (National University of Singapore, SG) [dblp]
- Stéphane Le Roux (University of Brussels, BE) [dblp]
- Alberto Marcone (University of Udine, IT) [dblp]
- Kenshi Miyabe (Meiji University - Kawasaki, JP) [dblp]
- Antonio Montalbán (University of California - Berkeley, US) [dblp]
- Carl Mummert (Marshall University - Huntington, US) [dblp]
- Eike Neumann (Aston University - Birmingham, GB) [dblp]
- Paulo Oliva (Queen Mary University of London, GB) [dblp]
- Ludovic Patey (University Paris-Diderot, FR) [dblp]
- Arno Pauly (University of Cambridge, GB) [dblp]
- Matthias Schröder (TU Darmstadt, DE) [dblp]
- Victor Selivanov (A. P. Ershov Institute - Novosibirsk, RU) [dblp]
- Paul Shafer (Ghent University, BE) [dblp]
- Dieter Spreen (Universität Siegen, DE) [dblp]
- Klaus Weihrauch (FernUniversität in Hagen, DE) [dblp]
- Keita Yokoyama (JAIST - Ishikawa, JP) [dblp]
- Kazuto Yoshimura (JAIST - Ishikawa, JP)
- Martin Ziegler (KAIST - Daejeon, KR) [dblp]
Related Seminars
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
