Approximate counting for complex-weighted Boolean constraint satisfaction problems
Approximate counting for complex-weighted Boolean constraint satisfaction problems
复制标题
复数加权布尔约束满足问题的近似计数
DOI：
10.1016/j.ic.2012.08.002
复制
发表时间：
2012
影响因子：
1
通讯作者：
Tomoyuki Yamakami
中科院分区：
文献类型：
--
作者：
T. Horiyama;T. Ito;K. Nakatsuka;A. Suzuki;R. Uehara;Tomoyuki Yamakami;Tomoyuki Yamakami
约束满足问题（或CSP）已经在例如人工智能、数据库理论、图论和统计物理学中被广泛研究。从实用的角度来看，近似求解这些CSP是有益的。当一个人试图近似的总数的真值分配，满足所有布尔值的约束（未加权）布尔CSP，有一个已知的分割定理，所有这样的计数问题整齐地分为三个类别下多项式时间（随机）近似保持减少。与此相反，我们得到了一个二分法定理的近似计数复加权布尔CSP，提供了所有复值一元约束可以自由使用。正是自由一元约束的表达能力使我们能够证明这样一个更强、更完备的分类定理。这一发现使所有计数CSP的近似复杂性分类的追求向前迈进了一步。为了处理复杂的权重，我们采用证明技术的因式分解和减少沿着线解决Holant问题。此外，我们引入了一个新的概念的T-可构造性，自然会导致近似保持约简。我们的结果也给出了一个近似模拟的二分法定理的复杂性的精确计数复加权布尔CSP。
Constraint satisfaction problems (or CSPs) have been extensively studied in, for instance, artificial intelligence, database theory, graph theory, and statistical physics. From a practical viewpoint, it is beneficial to approximately solve those CSPs. When one tries to approximate the total number of truth assignments that satisfy all Boolean-valued constraints for (unweighted) Boolean CSPs, there is a known trichotomy theorem by which all such counting problems are neatly classified into exactly three categories under polynomial-time (randomized) approximation-preserving reductions. In contrast, we obtain a dichotomy theorem of approximate counting for complex-weighted Boolean CSPs, provided that all complex-valued unary constraints are freely available to use. It is the expressive power of free unary constraints that enables us to prove such a stronger, complete classification theorem. This discovery makes a step forward in the quest for the approximation-complexity classification of all counting CSPs. To deal with complex weights, we employ proof techniques of factorization and arity reduction along the line of solving Holant problems. Moreover, we introduce a novel notion of T-constructibility that naturally induces approximation-preserving reducibility. Our result also gives an approximation analogue of the dichotomy theorem on the complexity of exact counting for complex-weighted Boolean CSPs.