Computational Aspects of Constructive and Probability Logic

In mathematical logic people study logical systems capturing various parts of formal reasoning. The main subject of this project is comprised by two kinds of nonclassical logic, namely constructive logic and probability logic. Constructive logic dates back to the beginnings of the twentieth century and tries to capture various forms of constructive mathematical reasoning. Right from the beginning people have tried to link this syntactical approach to constructivism with computational mathematics, for example by giving computational interpretations of the rules and axioms of constructive logic. This, however, turned out to be a difficult enterprise, and in fact all of the ideas to complete it initially failed, until Skvortsova proved in 1988 that the ideas of Kolmogorov and Medvedev could be successfully applied to obtain the desired computational semantics. The structure of Medvedev degrees that she used has many other applications in mathematical logic, and we plan to study the connections of this structure with constructive logic further. In particular we hope to better understand the relation with the theory of Pi-0-1 classes that has recently seen great progress in computability theory. Probability logic is a much newer and less canonical kind of logic, that nevertheless poses many fundamental questions about the logical and computational nature of probability. In this project we focus on one specific kind of probability logic that is based on Valiants famous pac-model, a model of induction that has become the dominant paradigm in complexity theory and related areas. Here we seek to develop the basic theory of this logic, and in particular to determine the computational complexity of several of the decision problems related to it. In order to do this it will be crucial to develop at the same time its model theory and proof theory, which is immediately related to several intricacies from probability and measure theory.

In mathematical logic people study logical systems capturing various parts of formal reasoning. The main subject of this project is comprised by two kinds of nonclassical logic, namely constructive logic and probability logic. Constructive logic dates back to the beginnings of the twentieth century and tries to capture various forms of constructive mathematical reasoning. Right from the beginning people have tried to link this syntactical approach to constructivism with computational mathematics, for example by giving computational interpretations of the rules and axioms of constructive logic. This, however, turned out to be a difficult enterprise, and in fact all of the ideas to complete it initially failed, until Skvortsova proved in 1988 that the ideas of Kolmogorov and Medvedev could be successfully applied to obtain the desired computational semantics. The structure of Medvedev degrees that she used has many other applications in mathematical logic, and we plan to study the connections of this structure with constructive logic further. In particular we hope to better understand the relation with the theory of Pi-0-1 classes that has recently seen great progress in computability theory. Probability logic is a much newer and less canonical kind of logic, that nevertheless poses many fundamental questions about the logical and computational nature of probability. In this project we focus on one specific kind of probability logic that is based on Valiants famous pac-model, a model of induction that has become the dominant paradigm in complexity theory and related areas. Here we seek to develop the basic theory of this logic, and in particular to determine the computational complexity of several of the decision problems related to it. In order to do this it will be crucial to develop at the same time its model theory and proof theory, which is immediately related to several intricacies from probability and measure theory.