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 May 2019	Ends:	30 April 2022	Value (£):	362,033
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	Information Technologies
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 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