On the Complexity of Quantifier Elimination: the Structural Approach

DOI10.1093/comjnl/36.5.400zbMath0788.68058OpenAlexW2130164058MaRDI QIDQ3140550

Felipe Cucker

Publication date: 28 November 1993

Published in: The Computer Journal (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1093/comjnl/36.5.400

zbMATH Keywords

complexity of quantifier eliminationcomputations with real numbersmodel for parallel computationspolynomial hierarchy over the reals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Quantifier elimination, model completeness, and related topics (03C10)

Related Items

Separation of complexity classes in Koiran's weak model, Some Results on Interactive Proofs for Real Computations, A note on parallel and alternating time, On the computation of Boolean functions by analog circuits of bounded fan-in, On Relativizations of the P =? NP Question for Several Structures, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, Implicit complexity over an arbitrary structure: Quantifier alternations, On measures of space over real and complex numbers, On digital nondeterminism, Exotic quantifiers, complexity classes, and complete problems, On the parallel complexity of the polynomial ideal membership problem, Interactive proofs and a Shamir-like result for real number computations, Saturation and stability in the theory of computation over the reals, Real computations with fake numbers, Computational complexity of multi-player evolutionarily stable strategies