Approximating partition functions of bounded-degree Boolean counting Constraint Satisfaction Problems

Autor: Leslie Ann Goldberg, Andreas Galanis, Kuan Yang
Rok vydání: 2021
Předmět:
FOS: Computer and information sciences
Class (set theory)
Computer Networks and Communications
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
Computer Science::Computational Complexity
01 natural sciences
Theoretical Computer Science
Combinatorics
Computer Science - Data Structures and Algorithms
0202 electrical engineering
electronic engineering
information engineering
Data Structures and Algorithms (cs.DS)
Constraint satisfaction problem
Mathematics
000 Computer science
knowledge
general works
Degree (graph theory)
Applied Mathematics
Function (mathematics)
Exponential function
Computer Science - Computational Complexity
Computational Theory and Mathematics
010201 computation theory & mathematics
Bounded function
Computer Science
Bipartite graph
020201 artificial intelligence & image processing
Affine transformation
Zdroj: Journal of Computer and System Sciences. 115:187-213
ISSN: 0022-0000
DOI: 10.1016/j.jcss.2020.08.003
Popis: We study the complexity of approximate counting Constraint Satisfaction Problems (#CSPs) in a bounded degree setting. Specifically, given a Boolean constraint language $\Gamma$ and a degree bound $\Delta$, we study the complexity of #CSP$_\Delta(\Gamma)$, which is the problem of counting satisfying assignments to CSP instances with constraints from $\Gamma$ and whose variables can appear at most $\Delta$ times. Our main result shows that: (i) if every function in $\Gamma$ is affine, then #CSP$_\Delta(\Gamma)$ is in FP for all $\Delta$, (ii) otherwise, if every function in $\Gamma$ is in a class called IM$_2$, then for all sufficiently large $\Delta$, #CSP$_\Delta(\Gamma)$ is equivalent under approximation-preserving (AP) reductions to the counting problem #BIS (the problem of counting independent sets in bipartite graphs) (iii) otherwise, for all sufficiently large $\Delta$, it is NP-hard to approximate the number of satisfying assignments of an instance of #CSP$_\Delta(\Gamma)$, even within an exponential factor. Our result extends previous results, which apply only in the so-called "conservative" case.
Comment: To appear in JCSS. This version: minor corrections to typos
Databáze: OpenAIRE
Externí odkaz: