VPSPACE and a transfer theorem over the reals
From MaRDI portal
DOI10.1007/978-3-540-70918-3_36zbMath1213.68300arXivcs/0610009OpenAlexW2080148911MaRDI QIDQ626668
Sylvain Perifel, Pascal Koiran
Publication date: 18 February 2011
Published in: Computational Complexity, STACS 2007 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0610009
computational complexityalgebraic complexityBlum-Shub-Smale modelValiant's modelBlum-Shub-Smale model of computation
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)
Related Items (10)
Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Interpolation in Valiant's theory ⋮ Finding a vector orthogonal to roughly half a collection of vectors ⋮ Kolmogorov Complexity Theory over the Reals ⋮ Evaluating geometric queries using few arithmetic operations ⋮ Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes ⋮ VPSPACE and a transfer theorem over the complex field ⋮ Interactive proofs and a Shamir-like result for real number computations ⋮ A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant ⋮ Unifying known lower bounds via geometric complexity theory
This page was built for publication: VPSPACE and a transfer theorem over the reals
