VPSPACE and a transfer theorem over the complex field

DOI10.1016/J.TCS.2009.08.026MaRDI QIDQ1034531zbMATH OpenOpenAlexFDO

Authors 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

algebraic complexityBlum-Shub-Smale modelcomputational complexityValiant's model

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• VPSPACE and a Transfer Theorem over the Complex Field
• Transfer theorems via sign conditions
• Interpolation in Valiant's theory

Cites work

• Characterizing Valiant’s Algebraic Complexity Classes
• Completeness and reduction in algebraic complexity theory
• Finding a vector orthogonal to roughly half a collection of vectors
• scientific article; zbMATH DE number 1500505 (Why is no real title available?)
• scientific article; zbMATH DE number 1834636 (Why is no real title available?)
• scientific article; zbMATH DE number 781350 (Why is no real title available?)
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Power of Real Turing Machines over Binary Inputs
• Parallel Merge Sort
• Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
• Saturation and stability in the theory of computation over the reals
• Topological complexity of the range searching
• Valiant’s Model: From Exponential Sums to Exponential Products

Cited in

(6)

• Transfer theorems via sign conditions
• Small space analogues of Valiant's classes and the limitations of skew formulas
• VPSPACE and a Transfer Theorem over the Complex Field
• Interpolation in Valiant's theory
• Monotone classes beyond VNP
• Monotone classes beyond VNP

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1034531)