Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR12-103 | 16th August 2012 05:37

Testing Assignments of Boolean CSPs


Authors: Arnab Bhattacharyya, Yuichi Yoshida
Publication: 16th August 2012 14:42
Downloads: 2807


Given an instance $\mathcal{I}$ of a CSP, a tester for $\mathcal{I}$ distinguishes assignments satisfying $\mathcal{I}$ from those which are far from any assignment satisfying $\mathcal{I}$. The efficiency of a tester is measured by its query complexity, the number of variable assignments queried by the algorithm. In this paper, we characterize the hardness of testing Boolean CSPs according to the relations used to form constraints. In terms of computational complexity, we show that if a Boolean CSP is sublinear-query testable (resp., not sublinear-query testable), then the CSP is in $NL$ (resp., $P$-complete, $\oplus L$-complete or $NP$-complete) and that if a sublinear-query testable Boolean CSP is constant-query testable (resp., not constant-query testable), then counting the number of solutions of the CSP is in $P$ (resp., $\#P$-complete). The classification is done by showing an $\Omega(n)$ lower bound for testing Horn 3SAT and investigating Post's lattice, the inclusion structure of Boolean algebras associated with CSPs.

ISSN 1433-8092 | Imprint