Transparent Long Proofs: A First PCP Theorem for NPR
Transparent Long Proofs: A First PCP Theorem for NPR
复制标题
透明长证明：NPR 的第一个 PCP 定理
DOI：
10.1007/s10208-005-0142-1
复制
发表时间：
2004
影响因子：
3
通讯作者：
K. Meer
中科院分区：
文献类型：
--
作者：
K. Meer
摘要介绍并研究了真实的数算法的概率可查证明（PCP）的概念。我们的出发点是Blum、Shub和
Smale（BSS）和NP在该模型中的真实的模拟NPR。我们定义了一个简单的方式验证以及复杂性类PCPR（r（n），q（n））的BSS模型。据我们所知，我们的主要结果是NPR的第一PCP定理。它指出，NPR中的每个问题都有透明的长证明，即，NPR \subseteq PCPR（poly，1），其中poly表示单变量多项式函数类。所使用的技术扩展了[12]的思想，用于在所谓的有理域上自测试和自校正某些函数到真实的数上的更一般的域。后者产生于特定的NPR-完全问题，为此我们构造了所需形式的验证器。
AbstractWe introduce and study the notion of probabilistically checkable proofs (PCP) for real number algorithms. Our starting point is the computational model of Blum, Shub, and
Smale (BSS) and the real analogue NPR of NP in that model. We define in a straightforward manner verifiers as well as complexity classes PCPR(r(n),q(n)) for the BSS model. Our main result is, to the best of our knowledge, the first PCP theorem for NPR. It states that each problem in NPR has transparent long proofs, i.e.,NPR \subseteq PCPR(poly,1), where poly denotes the class of univariate polynomial functions. The techniques used extend ideas from [12] for self-testing and self-correcting certain functions over so-called rational domains to more general domains over the real numbers. The latter arise from the particular NPR-complete problem for which we construct a verifier of the required form.