http://www.dagstuhl.de/18361

02. – 07. September 2018, Dagstuhl Seminar 18361

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

Organisatoren

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)

Auskunft zu diesem Dagstuhl Seminar erteilen

Simone Schilke zu administrativen Fragen

Michael Gerke zu wissenschaftlichen Fragen

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

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.