Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9655956 | Electronic Notes in Theoretical Computer Science | 2005 | 13 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Klaus Meer,