An algebraic proof of the real number PCP theorem

DOI10.1016/J.JCO.2016.11.006MaRDI QIDQ2396715zbMATH OpenOpenAlexFDO

Authors Martijn Baartse, Klaus Meer

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)

Recommendations

• An Algebraic Proof of the Real Number PCP Theorem
• The PCP theorem for NP over the reals
• The PCP theorem for NP over the reals
• Automata, Languages and Programming
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)

Cites work

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

Cited in

(7)

• 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
• The PCP theorem for NP over the reals
• Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
• 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)