An Algebraic Proof of the Real Number PCP Theorem

DOI10.1007/978-3-662-48054-0_5zbMath1370.68104OpenAlexW2181088000MaRDI QIDQ2946376

Klaus Meer, Martijn Baartse

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48054-0_5

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)

Related Items (1)

An algebraic proof of the real number PCP theorem

Cites Work

• The PCP theorem for NP over the reals
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
• Almost Transparent Short Proofs for NPℝ
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Algebraic methods for interactive proof systems
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Testing Low Degree Trigonometric Polynomials
• Topics in real and complex number complexity theory
• The PCP theorem by gap amplification

This page was built for publication: An Algebraic Proof of the Real Number PCP Theorem