...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Electronic Colloquium on Computational Complexity >Constant rate PCPs for circuit-SAT with sublinear query complexity
【24h】

Constant rate PCPs for circuit-SAT with sublinear query complexity

机译：具有亚线性查询复杂性的Circuit-SAT恒定速率PCP

获取原文
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The PCP theorem (Arora et. al., J. ACM 45(1,3)) says that every NP-proof can be encoded to another proof, namely, a probabilistically checkable proof (PCP), which can be tested by a verifier that queries only a small part of the PCP. A natural question is how large is the blow-up incurred by this encoding, i.e., how long is the PCP compared to the original NP-proof. The state-of-the-art work of Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)) shows that one can encode proofs of length n by PCPs of length nlogO(1)n that can be verified using a constant number of queries. In this work, we show that if the query complexity is relaxed to n, then one can construct PCPs of length O(n) for circuit-SAT, and PCPs of length O(tlogt) for any language in NTIME(t).More specifically, for any 0">0 we present (non-uniform) probabilistically checkable proofs (PCPs) of length 2O(1)n that can be checked using n queries for circuit-SAT instances of size n. Our PCPs have perfect completeness and constant soundness. This is the first constant-rate PCP construction that achieves constant soundness with nontrivial query complexity (o(n)).Our proof replaces the low-degree polynomials in algebraic PCP constructions with tensors of transitive algebraic geometry (AG) codes. We show that the automorphisms of an AG code can be used to simulate the role of affine transformations which are crucial in earlier high-rate algebraic PCP constructions. Using this observation we conclude that any asymptotically good family of transitive AG codes over a constant-sized alphabet leads to a family of constant-rate PCPs with polynomially small query complexity. Such codes are constructed in the appendix to this paper for the first time for every message length, after they have been constructed for infinitely many message lengths by Stichtenoth [Trans. Information Theory 2006].
机译：PCP定理（Arora等，J。ACM 45（1,3））说，每个NP证明都可以编码为另一个证明，即概率可检验证明（PCP），可以由验证者进行测试仅查询PCP的一小部分。一个自然的问题是这种编码引起的爆破有多大，即PCP与原始的NP认证相比需要多长时间。 Ben-Sasson和Sudan（SICOMP 38（2））和Dinur（J. ACM 54（3））的最新工作表明，可以使用长度为nlogO（1）的PCP来编码长度为n的证明。 n可以使用恒定数量的查询进行验证。在这项工作中，我们表明如果将查询复杂度放宽到n，则可以在NTIME（t）中构造针对Circuit-SAT的长度为O（n）的PCP，对于任何语言构造为长度为O（tlogt）的PCP。更多具体来说，对于任何0 0，我们都会提供（长度为2O（1）n的（非均匀的）概率可检验证明（PCP），可以使用n个查询来查询大小为n的Circuit-SAT实例。我们的PCP具有完美的完整性和恒定稳健性。这是第一个以恒定的查询复杂度（o（n））实现恒定稳健性的恒定速率PCP构造。我们的证明用传递代数几何（AG）代码的张量替换了代数PCP构造中的低次多项式。我们表明，AG代码的自同构可用于模拟仿射变换的作用，仿射变换在早期的高速率代数PCP构造中至关重要，由此得出的结论是，在恒定大小上，任何渐近良好的传递AG代码族字母导致发多项式小查询复杂度的恒定速率PCP。在Stichtenoth [Trans。信息理论，2006]。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号