论文标题
当前无限域约束满意度中的挑战：无限绵羊的困境
Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep
论文作者
论文摘要
约束满意度问题（CSP）是一个计算问题，在其中我们获得了变量和限制。问题是是否可以分配变量值以使所有约束都得到满足。我们概述了CSP的当前研究状态，其中变量和约束的值是从预先固定的有限界限的均匀结构中获取的。我们解释了迄今为止的主要数学思想，即他们带来的三个困境，以及为克服它们而做些什么，以便获得对此类CSP的计算复杂性的满意理解。
A Constraint Satisfaction Problem (CSP) is a computational problem where we are given variables and constraints about them; the question is whether the variables can be assigned values such that all constraints are satisfied. We give an overview of the current state of research on CSPs where values for the variables and constraints are taken from a finitely bounded homogeneous structure which is fixed beforehand. We explain the main mathematical ideas so far, the three dilemmas they brought upon us, and what could be done to overcome them in order to obtain a satisfactory understanding of the computational complexity of such CSPs.
