Infinite-domain Constraint Satisfaction Problems

无限域约束满足问题

基本信息

批准号：
EP/L005654/1
负责人：
Barnaby Martin
金额：
$ 12.77万
依托单位：
Middlesex University
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2014
资助国家：
英国
起止时间：
2014 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FL005654%2F1
关键词：
Infinite domain Constraint Satisfaction Problems

项目摘要

Constraint Satisfaction Problems (CSPs) provide a powerful framework within which to phrase many computational problems from across Computer Science. In Combinatorics they are known as Homomorphism Problems and in Databases they appear as conjunctive-query containment. CSPs manifest in Artificial Intelligence in the form of temporal and spatial reasoning, and in Computational Linguistics in the guise of tree description languages. In Computational Biology, phylogenetic reconstruction is a CSP, and in Graph Theory it known as H-colouring. We propose to study the computational complexity of CSPs given by a single constraint language that may have an infinite domain. Research into the finite-domain case is now quite advanced, yet a great many interesting problems, which may not be given as finite-domain CSPs, may be given as infinite-domain CSPs. For example, this is true for most of the CSPs associated with Artificial Intelligence and Computational Linguistics. The computational complexity of most natural finite-domain CSPs is now known, yet many interesting infinite-domain CSPs have open complexity. For example, this is true of the Max Atoms problem, very closely related to Model-checking the mu-calculus, a problem of open complexity from the Verification community. It is also true of the Concatenation problem for free algebras, a problem arising in the Rewriting community. Further, a CSP was recently given that is polynomially equivalent with the elusive problem of Integer factoring. The commonality of structure across CSPs gives hope that we might find generic methods with which to analyse the computational complexity of these diverse problems. We will work on these problems specifically, as well as seeking to map out landscapes of complexity in such areas as the following. Linear Programming. Linear program feasibility is well-known to be polynomial-time solvable, How much extra expressive power can be added to linear program feasibility while maintaining its tractability?Integer programming. Integer program feasibility is well-known to be (NP-)hard to solve. How little expressive power does one need to take away to reach tractability?

约束满足问题（CSP）提供了一个强大的框架，可以在其中表达计算机科学领域的许多计算问题。在组合学中，它们被称为同态问题，在数据库中，它们显示为联合查询包含。 CSP 以时间和空间推理的形式出现在人工智能中，并以树描述语言的形式出现在计算语言学中。在计算生物学中，系统发育重建是一种CSP，在图论中它被称为H-着色。我们建议研究由可能具有无限域的单一约束语言给出的 CSP 的计算复杂性。现在对有限域情况的研究已经相当先进，但许多有趣的问题可能不会以有限域 CSP 的形式给出，但可以以无限域 CSP 的形式给出。例如，对于大多数与人工智能和计算语言学相关的 CSP 来说都是如此。大多数自然有限域 CSP 的计算复杂性现已已知，但许多有趣的无限域 CSP 具有开放复杂性。例如，最大原子问题就是如此，它与模型检查 mu 演算密切相关，这是验证社区的开放复杂性问题。自由代数的串联问题也是如此，这是重写社区中出现的一个问题。此外，最近给出了一个与难以捉摸的整数因式分解问题多项式等价的 CSP。 CSP 结构的共性给我们带来了希望，我们可能会找到通用方法来分析这些不同问题的计算复杂性。我们将专门解决这些问题，并寻求绘制出以下领域的复杂情况。线性规划。众所周知，线性规划的可行性是多项式时间可解的，在保持其易处理性的同时，可以为线性规划的可行性增加多少额外的表达能力？整数规划。众所周知，整数规划的可行性是（NP-）难以解决的。一个人需要降低多少表达能力才能达到易于驾驭的程度？