Structural tractability of enumerating CSP solutions
Structural tractability of enumerating CSP solutions
复制标题
枚举 CSP 解决方案的结构易处理性
作者：
G. Greco;Francesco Scarcello
决定CSP实例是否有解的问题在文献中得到了深入的研究，到目前为止已经得到了几个结构可追溯性的结果。然而，在实践中，约束满足是作为一个计算问题出现的，其重点要么是找到一个解决方案，要么是枚举所有解决方案，可能投射到某些给定的输出变量集。本文研究了枚举（可能是投影）解问题的结构可跟踪性，这里的可跟踪性指的是多项式延迟可计算，因为一般情况下可以计算许多指数解。提出了一个基于超图树投影概念的框架，该框架推广了所有基于将给定实例分解为合适的多项式时间可计算子问题的树状群的结构分解方法。对于输出变量是其规范的一部分的结构类，以及对于必须确保任何可能的输出变量集的可计算WPD的结构类，都获得了可跟踪性结果。通过展示二分类，这些结果对于具有有界性的结构类是紧密的。
The problem of deciding whether CSP instances admit solutions has been deeply studied in the literature, and several structural tractability results have been derived so far. However, constraint satisfaction comes in practice as a computation problem where the focus is either on finding one solution, or on enumerating all solutions, possibly projected to some given set of output variables. The paper investigates the structural tractability of the problem of enumerating (possibly projected) solutions, where tractability means here computable with polynomial delay (WPD), since in general exponentially many solutions may be computed. A framework based on the notion of tree projection of hypergraphs is considered, which generalizes all structural decomposition methods that are based on decomposing a given instance into suitable tree-like groups of polynomial-time computable subproblems. Tractability results have been obtained both for classes of structures where output variables are part of their specification, and for classes of structures where computability WPD must be ensured for any possible set of output variables. By exhibiting dichotomies, these results are shown to be tight for classes of structures having bounded arity.