Article ID Journal Published Year Pages File Type
9655956 Electronic Notes in Theoretical Computer Science 2005 13 Pages PDF
Abstract
Probabilistically checkable proofs (PCPs) have turned out to be of great importance in complexity theory. On the one hand side they provide a new characterization of the complexity class NP, on the other hand they show a deep connection to approximation results for combinatorial optimization problems. In this paper we study the notion of PCPs in the real number model of Blum, Shub, and Smale. The existence of transparent long proofs for the real number analogue NPR of NP is discussed.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,