http://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

Simone Schilke for administrative matters

Michael Gerke for scientific matters

Motivation

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 reducibilities have been extended 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 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 really started to flourish after Gherardi and Marcone proposed it as a tool for a uniform approach to reverse analysis.

Another program for studying the complexity of mathematical problems is reverse mathematics, which aims to classify theorems according to the axioms that are needed to prove these theorems in second-order arithmetic. This proog-theoretic approach yields non-uniform classifications of the computational content of 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 motivated Dorais, Dzhafarov, Hirst, Mileti and Shafer, on the one hand, and Hirschfeldt and Jockusch, on the other hand, to study combinatorial problems using Weihrauch reducibility. 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. This has led to a number of exciting new ideas and results in what was previously already a very active and fruitful area.

The objectives of and the questions that should be addressed during the Dagstuhl Seminar fall into a number of different categories:

Classification of the Complexity of Problems

One part of the seminar will be devoted to the study of classifications of further computational problems in the Weihrauch lattice. A particular focus of this seminar will be on combinatorial problems such as Ramsey's theorem and variants thereof. Another hot topic of current research is the classification of probabilistic problems in the Weihrauch lattice and the presentation of further new results in this direction is anticipated too.

Higher Levels of the Weihrauch Lattice

A new active area of research is the study of higher levels of the Weihrauch lattice that correspond to the reverse mathematics systems above ACA_0, such as ATR_0. It has emerged that choice on Baire space and its unique counterpart are related to these systems and we expect that promising new research in this area that is currently on its way will be presented and further discussed at the Dagstuhl Seminar.

Structural Properties

We expect that structural and algebraic properties of the Weihrauch lattice will be subject of intensive discussion at the meeting alongside with the presentation of new classification results of specific problems.

License
  Creative Commons BY 3.0 DE
  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

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