Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin

Journal article

We analyse the complexity of approximate counting constraint satisfactions problems #CSP(F), where F is a set of nonnegative rational-valued functions of Boolean variables. A complete classification is known if F contains arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and requiring only those to be in F. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. Furthermore, we also consider what happens if only the pinning functions are assumed to be in F. We show that any set of functions for which pinning is not sufficient to recover the two kinds of permissive unaries must either have a very simple range, or must satisfy a certain monotonicity condition. We exhibit a non-trivial example of a set of functions satisfying the monotonicity condition.

Authors: Backens, M; Bulatov, A; Goldberg, LA; McQuillan, C; Živný, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Journal of Computer and System Sciences
• Volume: 109
• Pages: 95-125
• Publication date: 2019-12-27
• Acceptance date: 2019-12-15
• DOI: 10.1016/j.jcss.2019.12.003
• EISSN: 1090-2724
• ISSN: 0022-0000
• Language: English
• Keywords: FFR; weak conservativity; constraint satisfaction; ferromagnetic two-spin; approximate counting