Oracle Computations in Descriptive Complexity
Source of Funding: British Council-Austria Academic
Research Collaboration (ARC) Programme
Descriptive Complexity is the main link between Computer Science and Finite Model Theory, and seeks to relate the computational complexity of a problem with its definability in an appropriate logic: that is, the resources, such as time and space, required to solve the problem are related with the ease of specifying the problem. As such, there are important applications in, for example, the design of database query languages, and the specification and verification of programs. In this project, we intend to build on past related research of the two project leaders and further investigate how the use of oracles in computational models ties in with the use of vectorized generalized quantifiers in a corresponding logic (intuitively, we hope to obtain an understanding of how allowing (possibly restricted) access to a powerful subroutine in a computation can be modelled in logic). In more detail, we wish to use logics with vectorized generalized quantifiers to capture complexity classes, or to prove that such a characterization can not exist, both in the presence and absence of built-in relations.