Promise Constraint Satisfaction Problem: Structure and Complexity

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

基本信息

  • 批准号:
    EP/X033201/1
  • 负责人:
  • 金额:
    $ 176.51万
  • 依托单位:
  • 依托单位国家:
    英国
  • 项目类别:
    Fellowship
  • 财政年份:
    2024
  • 资助国家:
    英国
  • 起止时间:
    2024 至 无数据
  • 项目状态:
    未结题

项目摘要

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-Hard优化问题的长期悬而未决的问题,特别是必须在多大程度上放松最优性需求才能保证可处理性。

项目成果

期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Andrei Krokhin其他文献

A note on supermodular sublattices in finite relatively complemented lattices
  • DOI:
    10.1007/s00012-008-2123-8
  • 发表时间:
    2008-10-11
  • 期刊:
  • 影响因子:
    0.600
  • 作者:
    Andrei Krokhin;Benoit Larose
  • 通讯作者:
    Benoit Larose
Complexity of Clausal Constraints Over Chains
  • DOI:
    10.1007/s00224-007-9003-z
  • 发表时间:
    2007-09-28
  • 期刊:
  • 影响因子:
    0.400
  • 作者:
    Nadia Creignou;Miki Hermann;Andrei Krokhin;Gernot Salzer
  • 通讯作者:
    Gernot Salzer
CSP duality and trees of bounded pathwidth
  • DOI:
    10.1016/j.tcs.2010.05.016
  • 发表时间:
    2010-07-17
  • 期刊:
  • 影响因子:
  • 作者:
    Catarina Carvalho;Víctor Dalmau;Andrei Krokhin
  • 通讯作者:
    Andrei Krokhin

Andrei Krokhin的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('Andrei Krokhin', 18)}}的其他基金

The Complexity of Promise Constraint Satisfaction
承诺约束满足的复杂性
  • 批准号:
    EP/R034516/1
  • 财政年份:
    2018
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Research Grant
Robustly Tractable Constraint Satisfaction Problems
鲁棒可处理的约束满足问题
  • 批准号:
    EP/J000078/1
  • 财政年份:
    2012
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Research Grant
Submodular optimization, lattice theory and maximum constraint satisfaction problems
子模优化、格理论和最大约束满足问题
  • 批准号:
    EP/H000666/1
  • 财政年份:
    2010
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Research Grant
Descriptive Complexity of Constraints: An Algebraic Approach
约束的描述复杂性:代数方法
  • 批准号:
    EP/G011001/1
  • 财政年份:
    2008
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Research Grant
International Workshop on Mathematics of Constraint Satisfaction: Algebra, Logic, and Graph Theory
约束满足数学国际研讨会:代数、逻辑和图论
  • 批准号:
    EP/D036720/1
  • 财政年份:
    2006
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Research Grant

相似海外基金

CRII: AF: Streaming Approximability of Maximum Directed Cut and other Constraint Satisfaction Problems
CRII:AF:最大定向切割和其他约束满足问题的流近似性
  • 批准号:
    2348475
  • 财政年份:
    2024
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Standard Grant
AF:Small: Bayesian Estimation and Constraint Satisfaction
AF:Small:贝叶斯估计和约束满足
  • 批准号:
    2342192
  • 财政年份:
    2024
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Standard Grant
Hierarchical Geometric Accelerated Optimization, Collision-based Constraint Satisfaction, and Sensitivity Analysis for VLSI Chip Design
VLSI 芯片设计的分层几何加速优化、基于碰撞的约束满足和灵敏度分析
  • 批准号:
    2307801
  • 财政年份:
    2023
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Standard Grant
AF: Small: Streaming Complexity of Constraint Satisfaction Problems
AF:小:约束满足问题的流复杂性
  • 批准号:
    2152413
  • 财政年份:
    2022
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Standard Grant
Research in universal algebra: constraint satisfaction and residual properties
普适代数研究:约束满足和剩余性质
  • 批准号:
    RGPIN-2019-03931
  • 财政年份:
    2022
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Discovery Grants Program - Individual
Research and Development of a New SAT Solving Technologies for Constraint Satisfaction Problems
约束满足问题新型SAT求解技术的研究与开发
  • 批准号:
    22K11973
  • 财政年份:
    2022
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Algorithms and lower bounds for monotone dualization and tensor decomposition of constraint satisfaction hypergraphs
约束满足超图的单调对偶化和张量分解的算法和下界
  • 批准号:
    576241-2022
  • 财政年份:
    2022
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Alliance Grants
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
  • 批准号:
    RGPIN-2019-06522
  • 财政年份:
    2022
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Discovery Grants Program - Individual
Research in universal algebra: constraint satisfaction and residual properties
普适代数研究:约束满足和剩余性质
  • 批准号:
    RGPIN-2019-03931
  • 财政年份:
    2021
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Discovery Grants Program - Individual
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
概率图论和随机约束满足问题
  • 批准号:
    RGPIN-2019-06522
  • 财政年份:
    2021
  • 资助金额:
    $ 176.51万
  • 项目类别:
    Discovery Grants Program - Individual
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了