Promise Constraint Satisfaction Problem: Structure and Complexity

为什么有些计算问题承认算法总是工作得很快，也就是说，随着要处理的数据的大小很好地扩展，而其他计算问题不像这样，（似乎）只承认算法呈指数级扩展？回答这个问题是理论计算机科学的基本目标之一。计算复杂性理论将这两种问题分别形式化为可处理（或多项式时间可解）和np困难。因此，我们可以把上面的问题重新表述为：什么样的内在数学结构使计算问题易于处理？众所周知，这个非常普遍的问题是极其困难的。约束满足问题（CSP）及其变体被广泛用于回答这个问题，原因有两个：一方面，CSP框架非常通用，包括各种各样的计算问题，另一方面，该框架具有非常丰富的数学结构，为复杂性分类方法和算法技术提供了一个很好的实验室。所谓的CSP的代数方法在理解可追溯性的探索中非常成功。这种方法的思想是，问题实例中的某些代数结构（可以大致视为多维对称性）导致可处理性，而缺乏这种结构导致np硬度。这种方法已经提供了非常深刻的见解，并提供了非常强大的复杂性分类结果。特别是，它解释了在标准csp类中区分可处理问题和np困难问题的数学特征。提出的研究旨在通过揭示可处理性和np -硬度的更深层次的数学原因，将这种理解扩展到承诺约束满足问题，这是一个更大的问题类别，从而提供更有力的证据，证明可处理问题具有一定的代数结构。我们还将应用我们的新理论来解决一些关于经典NP-hard优化问题的长期悬而未决的问题，特别是最优性需求必须放松多少才能保证可追溯性。

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.