Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
An Algebraic Proof of the Real Number PCP Theorem
verfasst von : Martijn Baartse, Klaus Meer
Erschienen in: Mathematical Foundations of Computer Science 2015
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The PCP theorem has recently been shown to hold as well in the real number model of Blum, Shub, and Smale [3]. The proof given there structurally closely follows the proof of the original PCP theorem by Dinur [7]. In this paper we show that the theorem also can be derived using algebraic techniques similar to those employed by Arora et al. [1, 2] in the first proof of the PCP theorem. This needs considerable additional efforts. Due to severe problems when using low-degree algebraic polynomials over the reals as codewords for one of the verifiers to be constructed, we work with certain trigonometric polynomials. This entails the necessity to design new segmentation procedures in order to obtain well structured real verifiers appropriate for applying the classical technique of verifier composition.
We believe that designing as well an algebraic proof for the real PCP theorem on one side leads to interesting questions in real number complexity theory and on the other sheds light on which ingredients are necessary in order to prove an important result like the PCP theorem in different computational structures.