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

Miriam Backens, Andrei Bulatov, Leslie Ann Goldberg, Colin McQuillan, Stanislav Zivny

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)
85 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalJournal of Computer and System Sciences
Early online date27 Dec 2019
DOIs
Publication statusE-pub ahead of print - 27 Dec 2019

Keywords

  • approximate counting
  • constraint satisfaction
  • ferromagnetic two-spin
  • weak conservativity

Fingerprint

Dive into the research topics of 'Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin'. Together they form a unique fingerprint.

Cite this