An algebraic proof of the real number PCP theorem

DOI10.1016/J.JCO.2016.11.006zbMATH Open1370.68105OpenAlexW2559566311MaRDI QIDQ2396715FDOQ2396715

Klaus Meer, Martijn Baartse

Publication date: 24 May 2017

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2016.11.006

zbMATH Keywords

probabilistically checkable proofsreal number model of computationalgebraic proofsPCP theorem for NP over the realstesting trigonometric polynomials

Mathematics Subject Classification ID

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

Cites Work

• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Computational Complexity
• Proof verification and the hardness of approximation problems
• Probabilistic checking of proofs
• Some optimal inapproximability results
• Title not available (Why is that?)
• The PCP theorem by gap amplification
• The PCP theorem for NP over the reals
• An Algebraic Proof of the Real Number PCP Theorem
• Almost Transparent Short Proofs for NPℝ
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
• Testing Low Degree Trigonometric Polynomials
• Topics in real and complex number complexity theory

Cited In (5)

• Interactive proofs and a Shamir-like result for real number computations
• A PCP of proximity for real algebraic polynomials
• A Survey on Analog Models of Computation
• The PCP theorem for NP over the reals
• An Algebraic Proof of the Real Number PCP Theorem

This page was built for publication: An algebraic proof of the real number PCP theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396715)