EPSRC logo

Details of Grant 

EPSRC Reference: EP/S03238X/1
Title: Circuits, Logic and Symmetry
Principal Investigator: Dawar, Professor A
Other Investigators:
Researcher Co-Investigators:
Mr G B Wilsenach
Project Partners:
RWTH Aachen University
Department: Computer Science and Technology
Organisation: University of Cambridge
Scheme: Standard Research
Starts: 01 April 2019 Ends: 31 March 2022 Value (£): 362,033
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
Information Technologies
Related Grants:
Panel History:
Panel DatePanel NameOutcome
05 Mar 2019 EPSRC ICT Prioritisation Panel March 2019 Announced
Summary on Grant Application Form


The P vs NP conjecture is arguably one of the deepest

problems both in computer science and in science more generally. The conjecture

concerns the very act of problem solving itself, asking if the problems we think

are hard to solve are in fact hard, or if they admit some clever, efficiently

computable, solution. Put more technically, can we separate NP, a class

containing problems believed to be hard, from P, the class of efficiently

solvable problems. In order to make progress we need some understanding of what

it is about a problem that makes it efficiently solvable. In other words, we

need a `nice' characterization of P. This is a challenge because complexity

classes are defined using low-level machine models. These models are hard to

analyse and offer us little insight into the nature of the class. One approach

has been to develop alternative characterizations of complexity classes using

logics, which we think of as abstract high-level languages, rather than

low-level machine models. These logics work over abstract representations of

data, rather than binary strings and, crucially, respect the symmetries inherent

in that representation. These logical characterizations offer great insight into

what pieces of `abstract machinery' (e.g. recursion, counting operations, etc.)

are required to solve exactly those problems in a complexity class. We can now

frame our previous question more concretely: Is there a logic that characterizes

P?

This question is not only closeely related to the P vs NP conjecture, but

is itself a deep question about the nature of abstraction. In order to make

progress we would like to understand what differentiates the computational power

of high-level, abstract languages from that of low-level machines. Recent work

has shown that high-level programs define algorithms with a strong symmetry

property. In contrast, algorithms given by machine models are characterized by a

very weak symmetry condition. It follows that the relationship between these

models, and hence the central question of this field, can be reduced to a

question about the significance of the symmetry condition. In fact, recent

results have enabled us to ask fine-grained questions about the role of

symmetry, allowing us to use progressive weakenings of the symmetry requirement

in order to interpolate between the high-level languages and low-level

models.

The proposed work connects three fundamental approaches in complexity

theory, by exploring how symmetry plays a role in analysing complexity

in each case. They are circuit complexity, descriptive complexity and

proof complexity.

Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.cam.ac.uk