The complexity of approximating bounded-degree Boolean #CSP
The complexity of approximating bounded-degree Boolean #CSP
复制标题
近似有界度布尔值的复杂性
DOI：
10.1016/j.ic.2011.12.007
复制
发表时间：
2012
影响因子：
1
通讯作者：
Dyer M
中科院分区：
文献类型：
--
作者：
Dyer M
CSP实例的度是任何变量在约束范围中出现的最大次数。我们考虑了约束语言中包含两个一元常数关系{0}和{1}的有界度实例的布尔CSP的近似计数问题。当最大允许度足够大（至少6）时，我们得到了这个问题的复杂性的完整分类。如果约束语言中的每一个关系都是仿射的，则它在多项式时间内精确可解。如果每一个关系都可以表示为{0}、{1}和二元蕴涵的合取，则它等价于二部图中独立集的近似计数问题。否则，没有FPRAS，除非NP=RP。对于较低的度界，出现了其他情况，其中的复杂性与近似计数超图中的独立集的复杂性有关。
The degree of a CSP instance is the maximum number of times that any variable appears in the scopes of constraints. We consider the approximate counting problem for Boolean CSP with bounded-degree instances, for constraint languages containing the two unary constant relations {0} and {1}. When the maximum allowed degree is large enough (at least 6) we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial time if every relation in the constraint language is affine. It is equivalent to the problem of approximately counting independent sets in bipartite graphs if every relation can be expressed as conjunctions of {0}, {1} and binary implication. Otherwise, there is no FPRAS unless NP=RP. For lower degree bounds, additional cases arise, where the complexity is related to the complexity of approximately counting independent sets in hypergraphs.
登录
查看更多内容
DOI：
10.1137/100811258
发表时间：
2010-03
期刊：
SIAM J. Comput.
影响因子：
--
作者：
M. Dyer;David Richerby
通讯作者：
M. Dyer;David Richerby
DOI：
10.1145/2528400
发表时间：
2008-07
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
A. Bulatov
通讯作者：
A. Bulatov
一元二阶逻辑中可定义的图枚举问题的固定参数复杂度
DOI：
--
发表时间：
2000
期刊：
影响因子：
--
作者：
B. Courcellea;J. A. Makowskyb;U. Roticsc
通讯作者：
U. Roticsc
非负权有向图同态的可判定二分定理
影响因子：
1.4
作者：
Cai, Jin-Yi;Chen, Xi.
通讯作者：
Chen, Xi.
DOI：
--
发表时间：
1977
期刊：
International Colloquium on Automata, Languages and Programming
影响因子：
--
作者：
Janos Simon
通讯作者：
Janos Simon