Infinite-domain Constraint Satisfaction Problems

约束满足问题(CSP)提供了一个强大的框架，在这个框架内可以表达计算机科学中的许多计算问题。在组合学中，它们被称为同态问题，而在数据库中，它们表现为合取查询包容。CSP在人工智能中表现为时间和空间推理的形式，在计算语言学中表现为树描述语言的伪装。在计算生物学中，系统发育重建是一种CSP，在图论中它被称为H-染色。我们建议研究由可能具有无穷域的单一约束语言给出的CSP的计算复杂性。目前对有限域情形的研究已经相当深入，然而许多有趣的问题可能不会被给出为有限域CSP，而可能被给出为无限域CSP。例如，对于大多数与人工智能和计算语言学相关的CSP来说，情况就是如此。大多数自然有限域CSP的计算复杂性是已知的，然而许多有趣的无限域CSP具有开放的复杂性。例如，最大原子问题就是这样，它与模型检查u演算密切相关，这是一个来自验证社区的开放的复杂性问题。自由代数的级联问题也是如此，这是重写社区中出现的一个问题。此外，最近给出了一个CSP，它与难以捉摸的整数分解问题是多项式等价的。跨CSP的结构的共性给了我们希望，我们可能会找到通用的方法来分析这些不同问题的计算复杂性。我们将具体解决这些问题，并设法在以下领域绘制出复杂的图景。线性规划。众所周知，线性规划的可行性是多项式时间可解的，在保持线性规划的可解性的同时，又能为其增加多少表现力呢？整数规划。众所周知，整数规划的可行性是(NP-)难解的。一个人需要多小的表现力才能达到驯服的程度？

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?