Infinite-domain Constraint Satisfaction Problems

约束满足问题（csp）提供了一个强大的框架，在这个框架内，可以表达来自计算机科学领域的许多计算问题。在组合学中，它们被称为同态问题，而在数据库中，它们表现为连接查询包含。csp以时间和空间推理的形式出现在人工智能中，以树描述语言的形式出现在计算语言学中。在计算生物学中，系统发育重建是一个CSP，在图论中它被称为h着色。我们建议研究由单一约束语言给出的具有无限域的csp的计算复杂度。目前对有限域情况的研究已经相当深入，然而许多有趣的问题，可能不能用有限域csp来给出，而可以用无限域csp来给出。例如，大多数与人工智能和计算语言学相关的csp都是如此。大多数自然有限域csp的计算复杂度是已知的，然而许多有趣的无限域csp具有开放复杂度。例如，Max Atoms问题就是如此，它与模型检查mu演算密切相关，这是一个来自验证社区的开放复杂性问题。自由代数的Concatenation问题也是如此，这是重写社区中出现的一个问题。此外，最近给出了一个与整数分解问题多项式等价的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?