VPSPACE and a transfer theorem over the reals

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

zbMATH Keywords

computational complexityalgebraic complexityBlum-Shub-Smale modelValiant's modelBlum-Shub-Smale model of computation

Mathematics Subject Classification ID

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 (11)

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 ⋮ Monotone classes beyond VNP ⋮ 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