Transparent Long Proofs: A First PCP Theorem for NPR

We 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 NP_R of NP in that model. We define in a straightforward manner verifiers as well as complexity classes PCP_R(r(n),q(n)) for the BSS model. Our main result is, to the best of our knowledge, the first PCP theorem for NP_R. It states that each problem in NP_R has transparent long proofs, i.e.,NP_R subseteq PCP_R(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 NP_R-complete problem for which we construct a verifier of the required form.