首页    期刊浏览 2024年12月02日 星期一
登录注册

文章基本信息

  • 标题:Testing Assignments of Boolean CSPs
  • 本地全文:下载
  • 作者:Arnab Bhattacharyya ; Yuichi Yoshida
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2012
  • 卷号:2012
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Given an instance of a CSP, a tester for distinguishes assignments satisfying from those which are far from any assignment satisfying . 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, 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 (n) lower bound for testing Horn 3SAT and investigating Post's lattice, the inclusion structure of Boolean algebras associated with CSPs.

  • 关键词:Constraint satisfaction problems; Property Testing
国家哲学社会科学文献中心版权所有