Inexpressibility in Complex Structures using Diagonalization

Lead Research Organisation: University of Oxford
Department Name: Computer Science


Summary of the project: Diagonal arguments led to many successes of early complexity theory. In order to separate complexity classes one approach is to exhibit a language in one class that differs from every language available in the other class. This is usually performed using a query that can simulate everything else in the other class but gives a slightly different answer. One famous example is the time/space hierarchy theorem. Exploiting the simple local behaviour of Turing machines, it is possible to simulate other Turing machines without much overhead. This observation is enough to conclude that additional time/space, results in machines solving more problems.

Often the computational problem only concerns the abstract representation of the data, rather than a low-level list of zeros and ones encoding the input. An alternative characterization of complexity classes was developed, where the queries are members of different logics working on the structure itself. These logical characterizations offer great insight into what pieces of abstract machinery (e.g. recursion, order, counting operations etc.) are required to solve exactly those problems in a complexity class. Most commonly game theoretic or combinatorial arguments are used to find limitations of logic-based complexity classes, where the weakness of the model is exploited (symmetry, locality). These game theoretic arguments quickly become complicated as the signature of the structure or the logic increases. In this logic-based setting, results using diagonalization are less common. Diagonal arguments and simulation in logics appear to be harder as often the signature used in the abstract representation of the data is limited and because the evaluation of logical queries is non-sequential, in contrast to Turing machines working step by step. This means the approach mainly applies to rich enough signatures, giving us new insight into complexity theory.

The aim of this DPhil project is to understand further usage of diagonalization in logical complexity classes. A recent publication of Miklós Ajtai showed potential in this direction and we would like to explore this new idea, see the limitations. It is known that similar diagonal arguments in mathematics fail for simple signatures (for example Gödel's incompleteness theorem fails in Presburger arithmetic, only containing addition). One main objective is to find the minimum signature required for the method to work and using this knowledge, to apply the technique in various settings. The comparison between the computational resources needed for deterministic and nondeterministic computation is a central question in computational complexity. Nondeterminism has a simple representation in terms of logical quantifiers, and this new technique can extend our understanding of the fine border between deterministic and nondeterministic machines and logics. This project falls within the EPSRC Theoretical Computer Science research area, under ICT.


10 25 50

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/R513295/1 01/10/2018 30/09/2023
2421736 Studentship EP/R513295/1 01/10/2020 31/03/2024 Levente Sarah Bodnar