European Companies Search Engine
UK funding (£362,033): Circuits, Logic and Symmetry Ukri1 May 2019 UK Research and Innovation, United Kingdom
Overview
Text
Circuits, Logic and Symmetry
| Abstract | 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. |
| Category | Research Grant |
| Reference | EP/S03238X/1 |
| Status | Closed |
| Funded period start | 01/05/2019 |
| Funded period end | 31/12/2022 |
| Funded value | £362,033.00 |
| Source | https://gtr.ukri.org/projects?ref=EP%2FS03238X%2F1 |
Participating Organisations
| University of Cambridge | |
| RWTH Aachen University |
The filing refers to a past date, and does not necessarily reflect the current state. The current state is available on the following page: University of Cambridge, Cambridge.
