VPSPACE and a transfer theorem over the complex field

DOI10.1016/j.tcs.2009.08.026zbMath1176.68091OpenAlexW1899254311MaRDI QIDQ1034531

Pascal Koiran, Sylvain Perifel

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.026

zbMATH Keywords

computational complexityalgebraic complexityBlum-Shub-Smale modelValiant's model

Mathematics Subject Classification ID

Related Items (2)

Small space analogues of Valiant's classes and the limitations of skew formulas ⋮ Interpolation in Valiant's theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• VPSPACE and a transfer theorem over the reals
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Saturation and stability in the theory of computation over the reals
• Completeness and reduction in algebraic complexity theory
• Topological complexity of the range searching
• Finding a vector orthogonal to roughly half a collection of vectors
• Parallel Merge Sort
• On the Power of Real Turing Machines over Binary Inputs
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• Characterizing Valiant’s Algebraic Complexity Classes
• Valiant’s Model: From Exponential Sums to Exponential Products

This page was built for publication: VPSPACE and a transfer theorem over the complex field