The expressibility of functions on the boolean domain, with applications to counting CSPs
The expressibility of functions on the boolean domain, with applications to counting CSPs
复制标题
DOI：
10.1145/2528401
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
A. Bulatov;M. Dyer;L. A. Goldberg;M. Jerrum;Colin McQuillan
中科院分区：
文献类型：
--
作者：
A. Bulatov;M. Dyer;L. A. Goldberg;M. Jerrum;Colin McQuillan
关系克隆是研究约束满足问题(CSP)复杂性的一个重要工具，关系克隆是指在一组特定的基本关系上可以用本原正公式表示的所有关系的集合。POST格给出了所有布尔关系克隆的完全分类，并已用于对CSP的计算难度进行分类。出于了解(加权)计数CSP的计算复杂性的愿望，我们发展了一个类似的功能克隆的概念，并研究了这些克隆的情况。其中一个克隆是对数超模(LSM)函数的集合，它在对计数CSP进行分类方面发挥了重要作用。在保守情况下(其中所有非负一元函数都可用)，我们证明了在LSM函数的克隆和总克隆(包含所有函数)之间没有功能克隆。因此，任何包含单个非平凡非LSM函数的计数CSP在计算上都和#P中的任何问题一样难以逼近。此外，我们证明了任何非平凡函数克隆(在某种意义上将被精确地)包含二元函数“蕴含”。因此，在保守的情况下，所有非平凡的计数CSP都像#BIS一样难以逼近，#BIS是二部图中计算独立集的问题。鉴于复杂性理论的结果，自然会问“隐含”克隆是否等同于LSM函数的克隆。我们利用Möbius变换和傅立叶变换证明了这些克隆精确地重合到3。LSM克隆是否有限生成是一个有趣的开放问题。最后，我们研究了只有有限类一元函数可用的函数克隆。
An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. One of these clones is the collection of log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In the conservative case (where all nonnegative unary functions are available), we show that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function “implies”. As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the “implies” clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available.