Query efficient PCPs with perfect completeness
Query efficient PCPs with perfect completeness
复制标题
查询高效且完整的 PCP
DOI：
--
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Subhash Khot
中科院分区：
文献类型：
--
作者：
J. Håstad;Subhash Khot
对于每个整数k> 1，我们都会提供NP的PCP表征，其中验证者使用对数随机性，查询4K+K/ sup 2/位，在证明中，接受具有概率1的正确证明（即它具有完美的完整性）和接受具有一定最大概率的虚假语句的任何假定证明。特别是，对于任意小的常数/spl delta/> 0，验证者达到了1+/spl delta/1+/spl delta/的最佳摊销查询复杂性。 A. Samorodnitsky和L. Trevisan（2000）已经证明了这种特征，但是他们的验证者失去了完美的完整性，并且证明其证明是对此功能的必要用途。通过使用自适应验证者，我们可以将查询位数量减少到2k+k/sup 2/，samorodnitsky和trevisan获得的数字相同。最后，我们将一些结果扩展到较大的域。
For every integer k>1, we present a PCP characterization of NP where the verifier uses logarithmic randomness, queries 4k+k/sup 2/ bits in the proof, accepts a correct proof with probability 1 (i.e. it is has perfect completeness) and accepts any supposed proof of a false statement with a certain maximum probability. In particular, the verifier achieves optimal amortized query complexity of 1+/spl delta/ for arbitrarily small constant /spl delta/>0. Such a characterization was already proved by A. Samorodnitsky and L. Trevisan (2000), but their verifier loses perfect completeness and their proof makes an essential use of this feature. By using an adaptive verifier, we can decrease the number of query bits to 2k+k/sup 2/, the same number obtained by Samorodnitsky and Trevisan. Finally, we extend some of the results to larger domains.