TY - JOUR

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

AU - Backens, Miriam

AU - Bulatov, Andrei

AU - Goldberg, Leslie Ann

AU - McQuillan, Colin

AU - Zivny, Stanislav

PY - 2019/12/27

Y1 - 2019/12/27

N2 - 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 in the conservative case, where F is assumed to contain arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and adding only those to F : this is weak conservativity. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. In a further weakening of conservativity, we also consider what happens if only the pinning functions are assumed to be in F (instead of the two permissive unaries). 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.

AB - 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 in the conservative case, where F is assumed to contain arbitrary unary functions. We strengthen this result by fixing any permissive strictly increasing unary function and any permissive strictly decreasing unary function, and adding only those to F : this is weak conservativity. The resulting classification is employed to characterise the complexity of a wide range of two-spin problems, fully classifying the ferromagnetic case. In a further weakening of conservativity, we also consider what happens if only the pinning functions are assumed to be in F (instead of the two permissive unaries). 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.

KW - approximate counting

KW - constraint satisfaction

KW - ferromagnetic two-spin

KW - weak conservativity

UR - http://www.scopus.com/inward/record.url?scp=85077394918&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2019.12.003

DO - 10.1016/j.jcss.2019.12.003

M3 - Article

SN - 0022-0000

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

ER -