Descriptive complexity of polylogarithmic time

• Senén André González Cornejo

During the last forty years logics over finite structures have become a central pillar for studying the definability and complexity of computational problems. The focus is on understanding how the expressive power of logics over finite structures, or equivalently query languages over relational databases, relate to natural classes of computational complexity. Since then most Turing complexity classes have been characterized in terms of the expressive power of logic languages. 

In this context, higher-order logics provide natural and high levels of expressive power. A simple example which illustrates this point is the provided by the setcontainment join. A query that asks whether a patient has all the symptoms associated to a given disease, can be written literally provided the query language has the appropriate second-order constructs. By contrast, in first-order logic we cannot write this literally. Unfortunately, the high expressiveness of higher-order logic also yields a high complexity of evaluation of formulae as already shown by the famous Fagin-Stockmeyer theorems, which in principle make them not suitable for practical purposes. 

This leads us to the central theme of this PhD thesis, namely, to investigate new features of higher-order logics that have a real impact on their descriptive complexity, identifying cases in which the high expressiveness of higher-order logics over finite structures can be decoupled from their high complexity of evaluation. 

The main results presented in the thesis concern fragments of higher-order formal languages (including logics, query languages and formal models of machines) defined by means of semantic restrictions on the (higher-order) relations as well as the computational complexity yielded by those restrictions. 

We define novel and natural fragments of higher-order logics of order three and above, restricting the interpretation of higher-order variables to higher-order relations of polynomial size. We constructively show that the expressive power of all these fragments collapse to second-order logic. These fragments enable clear and concise definitions of problems that, when expressed in lower order logics, result in extremely complicated sentences which require intricate encodings. Further restricting the interpretation of second-order variables to relations of polylogarithmic size, we then introduce restricted second-order and fixed-point logics which give an elegant and precise descriptive characterization of polylogarithmic complexity classes, most prominently of non-deterministic and deterministic polylogarithmic time. We demonstrate the relevance of these logics and complexity classes by several problems in database theory, proving lower bounds for the expressibility and complexity.

Additionally, we contributed to the development of a tractable higher-order language to model and query semantic Web data and demonstrated how our research in restricted higher-order logics can be applied for systematic refinement in the context of the ASM method for high-level systems design and analysis.