Measuring the Complexity of Computational Content: Weihrauch Reducibility and Reverse Analysis

Motivation

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 eld 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 ner uniform structure that is yet in basic agreement with the non-uniform results of reverse mathematics, despite some subtle di erences.

Likewise one could expect relations between weak complexity theoretic versions of arith- metic 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.

Topics of Interest

• 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.