University of Leicester

informatics

Oracle Computations in Descriptive Complexity

Source of Funding: British Council-Austria Academic Research Collaboration (ARC) Programme
Amount: 1,500
Duration: September 1996 - August 1997
Principal Investigators: Prof. Dr. Georg Gottlob (TU Vienna, Austria), Prof. Iain Stewart
Other Investigators: Dr. Juha Nurmonen, Dr. Helmut Veith (TU Vienna, Austria), Mr. Richard Gault

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.

University of Leicester 15th December 2000. Last modified: 8th January 2004, 14:33:13.
Informatics Web Maintainer. This document has been approved by the Head of Department.