Log-supermodular functions, functional clones and counting CSPs

Details Log-supermodular functions, functional clones and counting CSPs Log-supermodular functions, functional clones and counting CSPs

2011-08-26

arxiv.org/abs/1108.5288v2

Computer Science

Computational Complexity

small corrections

Scientific paper

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 log-supermodular (lsm) functions, which turns out to play a significant role in classifying counting CSPs. In our study, we assume that non-negative unary functions (weights) are available. Given this, we prove that there are no functional clones lying strictly between the clone of lsm functions and the total clone (containing all functions). Thus, any counting CSP that contains a single nontrivial non-lsm function is computationally as hard as any problem in #P. Furthermore, any non-trivial functional clone (in a sense that will be made precise below) contains the binary function "implies". As a consequence, all non-trivial counting CSPs (with non-negative unary weights assumed to be available) are computationally at least as difficult as #BIS, the problem of counting independent sets in a bipartite graph. There is empirical evidence that #BIS is hard to solve, even approximately. Finally, we investigate functional clones in which only restricted unary functions (either favouring 0 or 1) are available.

Affiliated with

Also associated with

No associations

Rating

Log-supermodular functions, functional clones and counting CSPs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Log-supermodular functions, functional clones and counting CSPs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Log-supermodular functions, functional clones and counting CSPs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-502130