Promise Constraint Satisfaction Problem: Structure and Complexity

承诺约束满足问题：结构和复杂性

• 批准号: EP/X033201/1
• 负责人: Andrei Krokhin
• 金额: $ 176.51万
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2024
• 资助国家: 英国
• 起止时间: 2024 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FX033201%2F1
• 关键词: Promise; Constraint; Satisfaction; Problem; Structure

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 polynomial-time solvable) and NP-hard, 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 so-called 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 multi-dimensional symmerties) in problem instances leads to tractability, while the absence of such structure leads to NP-hardness. 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 NP-hard 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 NP-hardness, thus providing stronger evidence that tractable problems share a certain algebraic structure. We will also apply our new theory to resolve long-standing open questions about some classical NP-hard optimisation problems, specifically how much the optimality demand must be relaxed there to guarantee tractability.

为什么有些计算问题允许算法总是快速运行，即随着要处理的数据大小而很好地扩展，而其他计算问题则不然，并且（似乎）只允许指数级扩展的算法？回答这个问题是理论计算机科学的基本目标之一。计算复杂性理论将两类问题分别形式化为可处理（或多项式时间可解）和 NP 困难问题。因此，我们可以将上述问题改写如下：什么样的固有数学结构使得计算问题易于处理？众所周知，这个非常普遍的问题非常困难。约束满足问题（CSP）及其变体被广泛用于回答这个问题，原因有两个：一方面，CSP 框架非常通用，包括各种各样的计算问题，另一方面，该框架具有非常丰富的数学结构为复杂性分类方法和算法技术提供了优秀的实验室。所谓的 CSP 代数方法在理解易处理性方面非常成功。这种方法的想法是，问题实例中的某些代数结构（可以粗略地视为多维对称性）会导致易处理性，而缺乏这种结构会导致 NP 困难。这种方法已经提供了非常深入的见解，并提供了非常强大的复杂性分类结果。特别是，它解释了哪些数学特征可以区分标准 CSP 类别中的易处理问题和 NP 难题。拟议的研究旨在通过揭示可处理性和 NP 难度的更深层次数学原因，将这种理解扩展到承诺约束满足问题（这是一个更大的问题类别），从而提供更有力的证据来证明可处理问题共享某种代数结构。我们还将应用我们的新理论来解决有关一些经典 NP 难优化问题的长期悬而未决的问题，特别是必须放宽多少最优性要求才能保证可处理性。