EPSRC Reference: 
EP/X033201/1 
Title: 
Promise Constraint Satisfaction Problem: Structure and Complexity 
Principal Investigator: 
Krokhin, Professor A 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Computer Science 
Organisation: 
Durham, University of 
Scheme: 
EPSRC Fellowship 
Starts: 
01 February 2024 
Ends: 
31 January 2029 
Value (£): 
1,385,237

EPSRC Research Topic Classifications: 
Algebra & Geometry 
Fundamentals of Computing 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
Why is it that some computational problems admit algorithms that always work fast, that is, scale up well with the size of data to be processed, while other computational problems are not like this and (appear to) admit only algorithms that scale up exponentially? Answering this question is one of the fundamental goals of Theoretical Computer Science. Computational complexity theory formalises the two kinds of problems as tractable (or polynomialtime solvable) and NPhard, respectively. So we can rephrase the above question as follows: What kind of inherent mathematical structure makes a computational problem tractable? This very general question is known to be extremely difficult. The Constraint Satisfaction Problem (CSP) and its variants are extensively used towards answering this question for two reasons: on the one hand, the CSP framework is very general and includes a wide variety of computational problems, and on the other hand, this framework has very rich mathematical structure providing an excellent laboratory both for complexity classification methods and for algorithmic techniques.
The socalled algebraic approach to the CSP has been very successful in this quest for understanding tractability. The idea of this approach is that certain algebraic structure (which can viewed roughly as multidimensional symmerties) in problem instances leads to tractability, while the absence of such structure leads to NPhardness. This approach has already provided very deep insights and delivered very strong complexity classification results. In particular, it explained which mathematical features distinguish tractable and NPhard problems within the class of standard CSPs. The proposed research will aim to extend this understanding to Promise Constraint Satisfaction Problems, which is a much larger class of problems, by uncovering deeper mathematical reasons for tractability and NPhardness, thus providing stronger evidence that tractable problems share a certain algebraic structure. We will also apply our new theory to resolve longstanding open questions about some classical NPhard optimisation problems, specifically how much the optimality demand must be relaxed there to guarantee tractability.

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: 
