文章基本信息

标题：A Combinatorial Consistency Lemma with application to the PCP Theorem
本地全文：下载
作者：Oded Goldreich, Muli Safra
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：The current proof of the PCP Theorem (i.e., NP=PCP(log,O(1))) is very complicated. One source of difficulty is the technically involved analysis of low-degree tests. Here, we refer to the difficulty of obtaining strong results regarding low-degree tests; namely, results of the type obtained and used by Arora and Safra and Arora~et.~al. In this paper, we eliminate the need to obtain such strong results on low-degree tests when proving the PCP Theorem. Although we do not get rid of low-degree tests altogether, using our results it is now possible to prove the PCP Theorem using a simple analysis of low-degree tests (which yields weaker bounds). In other words, we replace the complicated algebraic analysis of low-degree tests presented by Arora and Safra and Arora~et.~al. by an intuitive combinatorial lemma (which does not refer to low-degree tests or polynomials).