EPSRC logo

Details of Grant 

EPSRC Reference: EP/X03190X/1
Title: Algebraic Methods for Quantified Constraints
Principal Investigator: Martin, Dr B D
Other Investigators:
Carvalho, Dr C Chen, Dr H
Researcher Co-Investigators:
Project Partners:
Department: Computer Science
Organisation: Durham, University of
Scheme: Standard Research
Starts: 01 January 2024 Ends: 31 December 2026 Value (£): 520,766
EPSRC Research Topic Classifications:
Fundamentals of Computing
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:
Panel DatePanel NameOutcome
24 Apr 2023 EPSRC ICT Prioritisation Panel April 2023 Announced
24 Jan 2023 EPSRC ICT Prioritisation Panel January 2023 Announced
Summary on Grant Application Form
The constraint satisfaction problem (CSP) is a paradigm in which it is possible to express, in a natural way, a wide range of problems arising in many areas of Computer Science and beyond, e.g. Artificial Intelligence, Computational Linguistics, Computational Biology, Combinatorics and Databases. A CSP instance involves a finite set of variables, a set of values (the domain) and a finite set of constraints. The task is to assign the variables to the values so as to satisfy all of the constraints. The CSP can be seen as a model-checking problem for the fragment of first-order logic that has just existential quantification, conjunction and equality. When universal quantification is added, the new paradigm is the quantified constraint satisfaction problem (QCSP). When the problem is parameterised by the language of constraints permitted, one finds for some types of constraint, the task of finding a solution is computationally easy (i.e. requires a feasible amount of computational resources such as running time and memory), but for many types, it is computationally hard. The complexity classification across finite constraint languages for the CSP was completed in 2017, independently by Bulatov and Zhuk, and is now known to be a dichotomy between polynomial time and NP-complete. The similar classification problem for the QCSP represents the only connective-based syntactic fragment of first-order logic where the outcome is not known. Recently, Zhuk and Martin (2019) refuted the Chen Conjecture that only complexities of polynomial time, NP-complete and Pspace-complete would in this classification. It is now known that exotic complexity classes such as DP-complete, Theta^P_2-complete and Pi^P_2-complete can be realised in QCSPs. Zhuk and Martin (2019) completed the three-element domain classification as a tetrachotomy between polynomial time, NP-complete, co-NP-complete and Pspace-complete. This proposal aims to take Zhuk's new methods beyond the three-element case to larger domains. The proposal will consider all finite domains, as well as some infinite domains where the constraint languages model notions from temporal reasoning. The central objective of the proposal is to map out landscapes of computational complexity across these constraint languages.

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
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
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: