ECCC-Report TR12-103https://eccc.weizmann.ac.il/report/2012/103Comments and Revisions published for TR12-103en-usThu, 16 Aug 2012 14:42:28 +0300
Paper TR12-103
| Testing Assignments of Boolean CSPs |
Arnab Bhattacharyya,
Yuichi Yoshida
https://eccc.weizmann.ac.il/report/2012/103Given 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.Thu, 16 Aug 2012 14:42:28 +0300https://eccc.weizmann.ac.il/report/2012/103