Functional Clones and Expressibility of Partition Functions
arXiv:1609.07377 · doi:10.1016/j.tcs.2017.05.001
Abstract
We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions ) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice.
arXiv comment42 pages, 6 figures; minor corrections
References in corpus (6)
- Simple universal models capture all classical spin physics
- Approximating the partition function of the ferromagnetic Potts model
- Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
- Inapproximability of the Tutte polynomial of a planar graph
- The expressibility of functions on the Boolean domain, with applications to Counting CSPs
- The complexity of approximating conservative counting CSPs