文章基本信息

标题：Probabilistically Checkable Proofs The Easy Way
本地全文：下载
作者：Marius Zimand
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present a weaker variant of the PCP Theorem that admits a significantly easier proof. In this variant the prover only has n t time to compute each bit of his answer, for an arbitray but fixed constant t , in contrast to being all powerful. We show that 3SAT is accepted by a polynomial-time probabilistic verifier that queries a constant number of bits from a polynomially long proof string. If a boolean formula of length n is satisfiable, then the verifier accepts with probability 1. If is not satisfiable, then the probability that a n t -bounded prover can fool the verifier is at most 1/2. The main technical tools used in the proof are the ``easy'' part of the PCP Theorem in which the verifier reads a constant number of bits from an exponentially long proof string, and the construction of a pseudo-random generator from a one-way permutation.
关键词：PCP Theorem , Probabilistically Checkable Proofs , Pseudo-Random Generators , Sampling