Sur la complexité du principe de Tarski-Seidenberg
From MaRDI portal
Publication:4713865
DOI10.24033/bsmf.2138zbMath0767.03017OpenAlexW136633354MaRDI QIDQ4713865
Pablo Solernó, Joos Heintz, Marie-Françoise Roy
Publication date: 25 June 1992
Published in: Bulletin de la Société mathématique de France (Search for Journal in Brave)
Full work available at URL: http://www.numdam.org/item?id=BSMF_1990__118_1_101_0
polynomial complexityreal closed fieldparallel modelsequential modelalgorithm for quantifier eliminationsimple exponential complexity
Analysis of algorithms and problem complexity (68Q25) Model-theoretic algebra (03C60) Global ground fields in algebraic geometry (14G25) Model theory of fields (12L12) Quantifier elimination, model completeness, and related topics (03C10)
Related Items
Learning from rounded-off data., Finding irreducible components of some real transcendental varieties, On the regularity of the minima of quasiconvex integrals, Un procédé d'élimination effective et quelques applications. (A procedure for effective elimination and some applications.), Metric properties of semialgebraic mappings, Complexity of stratifications of semi-Pfaffian sets, Generalized polar varieties: geometry and algorithms, Polar varieties, real equation solving, and data structures: the hypersurface case, Complexity lower bounds for computation trees with elementary transcendental function gates, Oscillation of linear ordinary differential equations: on a theorem of A. Grigoriev, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), An unfeasibility view of neural network learning, Condition number based complexity estimate for solving polynomial systems, Homogeneous multivariate polynomials with the half-plane property, Effective Łojasiewicz inequalities in semialgebraic geometry, Time-space tradeoffs in algebraic complexity theory, Deformation techniques for efficient polynomial equation solving., On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\), Polynomial bounds for the oscillation of solutions of Fuchsian systems, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, A Gröbner free alternative for polynomial system solving, On sign conditions over real multivariate polynomials, Unnamed Item, Complexity of computing the local dimension of a semialgebraic set, Saturation and stability in the theory of computation over the reals, Une borne optimale pour la programmation entière quasi-convexe, Real computations with fake numbers, Point searching in real singularcomplete intersection varieties: algorithms of intrinsic complexity, Description of the connected components of a semialgebraic set in single exponential time
Cites Work
- Thom's lemma, the coding of real algebraic numbers and the computation of the topology of semi-algebraic sets
- Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields
- On computing the determinant in small parallel time using a small number of processors
- Definability and fast quantifier elimination in algebraically closed fields
- The complexity of elementary algebra and geometry
- The complexity of linear problems in fields
- Solving systems of polynomial inequalities in subexponential time
- Real quantifier elimination is doubly exponential
- Complexity of deciding Tarski algebra
- A new decision method for elementary algebra
- Spécialisation de la suite de Sturm et sous-résultants (I)
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
