Almost Transparent Short Proofs for NPℝ
From MaRDI portal
Publication:3088268
DOI10.1007/978-3-642-22953-4_4zbMath1342.68138OpenAlexW1485819095MaRDI QIDQ3088268
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-22953-4_4
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)
Related Items (4)
An algebraic proof of the real number PCP theorem ⋮ An Algebraic Proof of the Real Number PCP Theorem ⋮ The PCP theorem for NP over the reals ⋮ A PCP of proximity for real algebraic polynomials
Cites Work
- Non-deterministic exponential time has two-prover interactive protocols
- Transparent long proofs: A first PCP theorem for \(\text{NP}_{\mathbb R}\)
- Some relations between approximation problems and PCPs over the real numbers
- Proof verification and the hardness of approximation problems
- Probabilistic checking of proofs
- Algebraic methods for interactive proof systems
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- The PCP theorem by gap amplification
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Almost Transparent Short Proofs for NPℝ
