The complexity of approximating conservative counting CSPs
作者：
Highlights：
• We classify the complexity of approximating conservative weighted counting CSP.
• It is in FP, as hard as counting bipartite independent sets (#BIS) or as hard as #SAT.
• For functions of arity 2, the #BIS-hard case is equivalent to #BIS.
• For higher arity, the #BIS-hard case reduces to a Boolean weighted #CSP or is NP-hard.
• Given a weighted constraint language, the classification is decidable.
摘要
•We classify the complexity of approximating conservative weighted counting CSP.•It is in FP, as hard as counting bipartite independent sets (#BIS) or as hard as #SAT.•For functions of arity 2, the #BIS-hard case is equivalent to #BIS.•For higher arity, the #BIS-hard case reduces to a Boolean weighted #CSP or is NP-hard.•Given a weighted constraint language, the classification is decidable.
论文关键词：Approximation,Counting complexity,Constraint satisfaction problems
论文评审过程：Received 3 April 2013, Revised 13 January 2014, Accepted 2 June 2014, Available online 27 June 2014.
论文官网地址：https://doi.org/10.1016/j.jcss.2014.06.006
