Interactive proofs and a Shamir-like result for real number computations
From MaRDI portal
Publication:2323360
DOI10.1007/s00037-018-0174-6zbMath1429.68075OpenAlexW2900435148WikidataQ113906243 ScholiaQ113906243MaRDI QIDQ2323360
Publication date: 30 August 2019
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-018-0174-6
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78) Other nonclassical models of computation (68Q09)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- VPSPACE and a transfer theorem over the reals
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Saturation and stability in the theory of computation over the reals
- Interactive protocols over the reals
- Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem
- The PCP theorem for NP over the reals
- An algebraic proof of the real number PCP theorem
- A note on parallel and alternating time
- Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
- On the Complexity of Quantifier Elimination: the Structural Approach
- Some Results on Interactive Proofs for Real Computations
- Algebraic methods for interactive proof systems
- IP = PSPACE
- COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
- Real Interactive Proofs for VPSPACE.
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
- Computational Complexity
- A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
This page was built for publication: Interactive proofs and a Shamir-like result for real number computations
