Descriptive Complexity of Constraints: An Algebraic Approach

约束的描述复杂性：代数方法

• 批准号: EP/G011001/1
• 负责人: Andrei Krokhin
• 金额: $ 3.33万
• 依托单位: Durham University
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2008
• 资助国家: 英国
• 起止时间: 2008 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FG011001%2F1
• 关键词: Descriptive; Complexity; Constraints; Algebraic; Approach

Constraint satisfaction problems have been widely studied in computer science because they can model many computational problems. Such problems are computationally hard in general, but some restrictions may ensure lower complexity. Descriptive complexity of a problem is measured by the richness of logical language necessary to describe the problem. As is well known, low descriptive complexity (that is, definability in a relatively weak logical language) implies low computational complexity (that is, relatively small amount of computational resources necessary to solve the problem).We propose to study descriptive complexity of restricted constraint satisfaction problems using the logic programming language Datalog and its fragments. This should lead to a better understanding of constraint satisfaction problems that require a small amount of space to solve them. We plan to combine methods from algebra, logic, and combinatorics to characterise constraint satisfaction problems with low descriptive complexity.

约束满足问题是计算机科学中的一个重要研究课题，因为它可以模拟许多计算问题。这样的问题通常在计算上是困难的，但是一些限制可以确保较低的复杂性。一个问题的描述复杂性是通过描述该问题所需的逻辑语言的丰富性来衡量的。众所周知，低描述复杂性（即，在一个相对较弱的逻辑语言的可定义性）意味着低计算复杂性（即，相对少量的计算资源所需的解决问题）。这将导致更好地理解约束满足问题，需要少量的空间来解决它们。我们计划结合联合收割机的方法，从代数，逻辑和组合，以低描述复杂性的约束满足问题。

项目成果

The Constraint Satisfaction Problem: Complexity and Approximability

• 发表时间: 2017
• 作者: A. Krokhin;Stanislav Živný

Caterpillar Duality for Constraint Satisfaction Problems

约束满足问题的 Caterpillar 对偶性

• DOI: 10.1109/lics.2008.19
• 发表时间: 2008
• 作者: Carvalho C

The complexity of constraint satisfaction games and QCSP

约束满足博弈和QCSP的复杂性

• DOI: 10.1016/j.ic.2009.05.003
• 发表时间: 2009
• 期刊: Information and Computation
• 影响因子: 1
• 作者: Börner F

The Complexity of the List Homomorphism Problem for Graphs

图的列表同态问题的复杂性

• DOI: 10.1007/s00224-011-9333-8
• 发表时间: 2011
• 期刊: Theory of Computing Systems
• 影响因子: 0.5
• 作者: Egri L

Two new homomorphism dualities and lattice operations

两个新的同态对偶性和晶格运算

• DOI: 10.1093/logcom/exq030
• 发表时间: 2010
• 期刊: Journal of Logic and Computation
• 影响因子: 0.7
• 作者: Carvalho C