On the Complexity of Quantifier Elimination: the Structural Approach
From MaRDI portal
complexity of quantifier eliminationcomputations with real numbersmodel for parallel computationspolynomial hierarchy over the reals
Quantifier elimination, model completeness, and related topics (03C10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)
Recommendations
- On the computational complexity and geometry of the first-order theory of the reals. III: Quantifier elimination
- Exotic Quantifiers, Complexity Classes, and Complete Problems
- Sur la complexité du principe de Tarski-Seidenberg
- On the computational complexity and geometry of the first-order theory of the reals. II: The general decision problem. Preliminaries for quantifier elimination
- Exotic quantifiers, complexity classes, and complete problems
Cited in
(25)- Exotic quantifiers, complexity classes, and complete problems
- On the parallel complexity of the polynomial ideal membership problem
- Saturation and stability in the theory of computation over the reals
- Separation of complexity classes in Koiran's weak model
- Deciding Hopf bifurcations by quantifier elimination in a software-component architecture
- Real computations with fake numbers
- On measures of space over real and complex numbers
- Computational complexity of multi-player evolutionarily stable strategies
- Interactive proofs and a Shamir-like result for real number computations
- A note on parallel and alternating time
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Implicit complexity over an arbitrary structure: Quantifier alternations
- The role of quantifier alternations in cut elimination
- Some results on interactive proofs for real computations
- Quantifier Elimination for Quantified Propositional Logics on Kripke Frames of Type
- scientific article; zbMATH DE number 5526522 (Why is no real title available?)
- On the combinatorial and algebraic complexity of quantifier elimination
- scientific article; zbMATH DE number 1490034 (Why is no real title available?)
- On digital nondeterminism
- On relativizations of the P =? NP question for several structures
- Exotic Quantifiers, Complexity Classes, and Complete Problems
- \(\mathcal M\)odular-\(\mathcal E\) and the role of elaboration tolerance in solving the qualification problem
- Logical Approaches to Computational Barriers
- Parallel time and quantifier prefixes
- On the computation of Boolean functions by analog circuits of bounded fan-in
This page was built for publication: On the Complexity of Quantifier Elimination: the Structural Approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140550)
