https://www.dagstuhl.de/18361

September 2 – 7 , 2018, Dagstuhl Seminar 18361

Measuring the Complexity of Computational Content: From Combinatorial Problems to Analysis

Organizers

Vasco Brattka (Universität der Bundeswehr – München, DE)
Damir D. Dzhafarov (University of Connecticut – Storrs, US)
Alberto Marcone (University of Udine, IT)
Arno Pauly (Swansea University, GB)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 8, Issue 9 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents

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 us to classify computational problems on real numbers and other continuous data types.

In the late 1980s Weihrauch has introduced a reducibility that can be seen as an analogue of many-one reducibility for (multi-valued) functions on infinite data types. This reducibility, now called Weihrauch reducibility, was studied since the 1990s by Weihrauch's school of computable analysis and flourished recently when Gherardi and Marcone proposed this reducibility as a tool for a uniform approach to reverse analysis.

Reverse mathematics aims to classify theorems according to the axioms that are needed to prove these theorems in second-order arithmetic. This proof theoretic approach yields non-uniform classifications of the computational content of certain theorems. However, many of these classifications also have uniform content and Weihrauch complexity allows us to study this uniform computational content directly using methods of computability theory.

This perspective has motivated Dorais, Dzhafarov, Hirst, Mileti and Shafer, on the one hand, Hirschfeldt and Jockusch, on the other hand, to study combinatorial problems using this approach. This research has led to a number of further reducibilities (computable reducibility, generalized Weihrauch reducibility and others) that can be seen as non-uniform or less resource sensitive versions of Weihrauch reducibility. Using this toolbox of reducibilities one can now adjust the instruments exactly according to the degree of uniformity and resource sensitivity that one wants to capture.

A precursor seminar (15392 Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis, see https://doi.org/10.4230/DagRep.5.9.77) that was also held at Dagstuhl has been instrumental in bringing together researchers from these different communities for the first time. This has created a common forum and fostered several research developments in this field. We believe that the current seminar was very successful in strengthening and deepening the collaborations between the involved communities. Ample time was left and successfully used for research in groups. A novelty of the current seminar was a special session at which solutions of open problems from the previous seminar were presented. To see that several of the major open problems of the previous meetings were solved in the meantime was inspiring and motivating! Some of the solutions involve new techniques with a wider applicability. Hopefully, we will see solutions to some of the open questions presented at the current seminar in the not too far future! Altogether, the seminar did proceed in a highly productive atmosphere, thanks to many excellent contributions from participants. Inspired by these contributions the organizers are planning to edit a special issue of the journal Computability dedicated to this seminar.

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 a bibliography on Weihrauch complexity that was started during the previous meeting and that saw significant growth in the meantime. 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!

Summary text license
  Creative Commons BY 3.0 Unported license
  Vasco Brattka, Damir D. Dzhafarov, Alberto Marcone, and Arno Pauly

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity
  • Verification / Logic

Keywords

  • Computability and complexity
  • Combinatorial problems
  • Reducibilities
  • Computational complexity
  • Reverse and constructive mathematics

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.