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-HARD。因此，我们可以将上述问题重新提出如下：什么样的固有数学结构使计算问题可以解决？众所周知，这个非常普遍的问题非常困难。约束满意度问题（CSP）及其变体被广泛用于回答此问题的原因有两个：一方面，CSP框架非常笼统，包括各种计算问题，另一方面，此框架具有非常丰富的数学结构，可为复杂性分类方法提供出色的实验室，用于算法的方法，并提供了algorithmic技术。在理解障碍性的过程中，所谓的代数方法非常成功。这种方法的想法是，在问题实例中，某些代数结构（可以大致认为是多维符号）会导致障碍，而缺乏这种结构会导致NP硬度。这种方法已经提供了非常深刻的见解，并提供了非常强大的复杂性分类结果。特别是，它解释了哪些数学特征区分了标准CSP类别中可拖动和NP硬性问题。拟议的研究旨在通过发现更深入的数学原因的障碍性和NP硬度，从而将这种理解扩展到承诺约束满意度问题，这是一个更大的问题，因此提供了更有力的证据，表明可拖动问题具有一定的代数结构。我们还将应用我们的新理论来解决有关某些经典NP-HARD优化问题的长期开放问题，特别是在那里必须放宽最佳需求以保证拖延性。