A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (Proc. 42nd German Conference on AI (KI-2019)) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints -- this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.
翻译:CSP 中一个限定的 CSP 实例的后门是一个变量集集, 每一个可能的快速化都会将其转换成一个多式时间可溶化的类 CSP 。 后门在人工智能和其他地方发现了许多应用, 因此对寻找这种后门的算法问题进行了深入的研究。 Sioutis 和 Janhunen (德国关于AI (KI-2019) 第42次会议) 提出了一个通用的后门概念, 适用于无限多式 CSP 案例, 而不是二进制限制。 我们将其概念概括为一大批允许更高性能限制的 CSP 类 CSP 概念。 我们显示, 这种无限式后门的后门具有许多积极的计算特性, 有限式后门的后门具有许多积极的计算特性: 相关的计算问题在基本约束语言( VI-2019) 时, 可以被固定的计算参数可移动。 我们显示, 无限的后门的检测问题是W[ 2 硬式和固定式的后门的可伸缩方法, 在标准的复杂度假设下可以排除。 我们显示, 后门的后门的硬式的硬式的货币关系有时会导致不易变的硬的硬性计算, 的递化的递化的递化的硬式的递化的递化的递化的递增缩的硬化的硬性变法 。