EPSRC Reference: 
EP/S03238X/1 
Title: 
Circuits, Logic and Symmetry 
Principal Investigator: 
Dawar, Professor A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science and Technology 
Organisation: 
University of Cambridge 
Scheme: 
Standard Research 
Starts: 
01 May 2019 
Ends: 
30 April 2022 
Value (£): 
362,033

EPSRC Research Topic Classifications: 
Fundamentals of Computing 


EPSRC Industrial Sector Classifications: 

Related Grants: 

Panel History: 
Panel Date  Panel Name  Outcome 
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 lowlevel 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 highlevel languages, rather than
lowlevel 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 highlevel, abstract languages from that of lowlevel machines. Recent work
has shown that highlevel 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 finegrained questions about the role of
symmetry, allowing us to use progressive weakenings of the symmetry requirement
in order to interpolate between the highlevel languages and lowlevel
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 nonacademic 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 