Log-supermodular functions, functional clones and counting CSPs
Log-supermodular functions, functional clones and counting CSPs
Motivated by a desire to understand the computational complexity of counting constraint satisfaction problems (counting CSPs), particularly the complexity of approximation, we study functional clones of functions on the Boolean domain, which are analogous to the familiar relational clones constituting Post's lattice. One of these clones is the collection of …