Functional Clones and Expressibility of Partition Functions

Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Živný

We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions $\{0,1\}^k\to\mathbb{R}_{\geq 0}$) 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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment