权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

The Complexity of Promise Constraint Satisfaction

承诺约束满足的复杂性

基本信息

批准号：
EP/R034516/1
负责人：
Andrei Krokhin
金额：
$ 56.22万
依托单位：
Durham University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2018
资助国家：
英国
起止时间：
2018 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FR034516%2F1
关键词：
Complexity Promise Constraint Satisfaction

项目摘要

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.

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