TR12-103 Authors: Arnab Bhattacharyya, Yuichi Yoshida

Publication: 16th August 2012 14:42

Downloads: 1932

Keywords:

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.