Presentation of Mikhail Rybakov's doctoral dissertation

On April 23, Mikhail Rybakov's doctoral thesis "Modeling logical systems by means of their fragments" was defended at the logic seminar of the Manin Laboratory of the Higher School of Modern Mathematics at the Moscow Institute of Physics and Technology.

Abstract 

The research is related to the algorithmic expressiveness of languages, logics, theories, and their fragments. 

Many natural logic systems are either algorithmically undecidable, or, being decidable, have a high complexity of the decision problem. It is known that certain restrictions imposed on the means of language, axiomatics, or semantics used lead to changes in the algorithmic complexity of certain tasks. At the same time, this is sometimes not the case: for example, in non-classical logics, both the undecidability and the high complexity of the decision problem in the case of decidability can be obtained with very strong restrictions on the means of the language. 

It seems relevant not only to find the boundaries within which such problems turn out to be algorithmically simple or, conversely, remain algorithmically complex, but also to develop general methods that make it possible to obtain estimates of the algorithmic complexity of fragments not only of particular logical systems, but of all systems of various infinite classes. Together with the methods, we would like to have common features or criteria that make it relatively easy to conclude about the algorithmic complexity of certain fragments of the system we are interested in, or at least about the potential possibility (or impossibility) of using these methods. 

The main purpose of the work is to develop general methods for modeling algorithmically complex problems within logics and theories using minimal language tools. In particular, the paper proposes methods for modeling complete languages by means of their very poor fragments. The language tools that are minimized include the following: the number of propositional variables in propositional languages, the number of individual variables, as well as the number and arity of predicate letters in first-order languages. Some restrictions on the use of logical connectives and quantifiers are also considered. 

The presentation will provide an overview of the results that the author has obtained in this area. The methods of obtaining them, as well as possible further advances, will be briefly described.