The Complexity of Promise Constraint Satisfaction

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

Why is it that some computational problems admit algorithms that always work fast, i.e. 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 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 non-trivial 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. It is a common perception that the power of this approach comes largely from the fact that symmetries can be composed, i.e. cascaded, to form another symmetry. The proposed researh will challenge this perception and extend the algebraic approach significantly beyond this seemingly indispensable property. Thus, we will provide further very strong evidence to the thesis that tractable problems posess 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.