NDLI: The expressibility of functions on the boolean domain, with applications to counting CSPs

Content Provider	ACM Digital Library
Author	Bulatov, Andrei A. Dyer, Martin Goldberg, Leslie Ann Jerrum, Mark Mcquillan, Colin
Copyright Year	2013
Abstract	An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base relations. Post's lattice gives a complete classification of all Boolean relational clones, and this has been used to classify the computational difficulty of CSPs. Motivated by a desire to understand the computational complexity of (weighted) counting CSPs, we develop an analogous notion of functional clones and study the landscape of these clones. 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 the conservative case (where all nonnegative unary functions are available), we show 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 to approximate as any problem in #P. Furthermore, we show that any nontrivial functional clone (in a sense that will be made precise) contains the binary function “implies”. As a consequence, in the conservative case, all nontrivial counting CSPs are as hard to approximate as #BIS, the problem of counting independent sets in a bipartite graph. Given the complexity-theoretic results, it is natural to ask whether the “implies” clone is equivalent to the clone of lsm functions. We use the Möbius transform and the Fourier transform to show that these clones coincide precisely up to arity 3. It is an intriguing open question whether the lsm clone is finitely generated. Finally, we investigate functional clones in which only restricted classes of unary functions are available.
Starting Page	1
Ending Page	36
Page Count	36
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/2528401
Journal	Journal of the ACM (JACM)
Volume Number	60
Issue Number	5
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2013-10-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Approximation algorithms Computational complexity Constraint satisfaction problems Counting problems
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The complexity of the counting constraint satisfaction problem

The Complexity of Finite-Valued CSPs

The complexity of conservative valued CSPs

The complexity of temporal constraint satisfaction problems

The expressibility of functions on the Boolean domain, with applications to Counting CSPs

Approximate Constraint Satisfaction Requires Large LP Relaxations

The complexity of homomorphism and constraint satisfaction problems seen from the other side

Log-supermodular functions, functional clones and counting CSPs

Robustness, stability, recoverability, and reliability in constraint satisfaction problems

The expressibility of functions on the boolean domain, with applications to counting CSPs

Similar Documents

The complexity of the counting constraint satisfaction problem

The Complexity of Finite-Valued CSPs

The complexity of conservative valued CSPs

The complexity of temporal constraint satisfaction problems

The expressibility of functions on the Boolean domain, with applications to Counting CSPs

Approximate Constraint Satisfaction Requires Large LP Relaxations

The complexity of homomorphism and constraint satisfaction problems seen from the other side

Log-supermodular functions, functional clones and counting CSPs

Robustness, stability, recoverability, and reliability in constraint satisfaction problems

The expressibility of functions on the boolean domain, with applications to counting CSPs