Complexity of computing the local dimension of a semialgebraic set
type: Item
instance of: scholarly article
title: Complexity of computing the local dimension of a semialgebraic set
zbMATH Open document ID: 0986.14036
published in: Journal of Symbolic Computation
publication date: 2000-07-18T00:00:00Z
review text: The author exhibits some new and some improved complexity bounds for the task of computing the global dimension \(\dim(V)\) of a semialgebraic set \(V\) given by polynomial inequalities, the local dimension \(\dim_x(V)\) of \(V\) at a given point \(x\in V\) and the dimension of the Zariski tangent space \(T_x(V)\) of \(V\) at \(x\). The paper starts with a description of the author's strictly personal view of the recent advances in the field: complexity theory in algorithmic algebraic and semialgebraic geometry (where the author's own contributions are seminal). Let \(V\subset{\mathbb R}^n\) be a semialgebraic set defined by \(K\) inequalities of \(n\)-variate polynomials with integer coefficients. Suppose that the degrees and logarithmic heights of these polynomials are bounded positive integers \(d\) and \(M\) respectively. Then \(\dim(V)\) can be determined using \(M^{O(1)}(Kd)^{O(\dim(V)\text{codim}(V))}=M^{O(1)}(Kd)^{O(n^2)}\) bit operations. In case that \(V\) is defined only by equations this bound can be improved to \(M^{O(1)}Kd^{O(\dim(V)\text{codim}(V))}=M^{O(1)}Kd^{O(n^2)}\) bit operations. Moreover, in this case, it is possible to find using \(M^{O(1)}Kd^{O(n^2)}\) bit operations a quantifier free formula in the language of ordered fields which defines the singular locus of the real variety \(V\). This formula contains \(d^{O(n^2)}\) polynomials of degree \(d^{O(n)}\) and logarithmic height \((log(K) M)^{O(1)}d^{O(n)}\) (theorems 3.1 and 5.1). Let \(x\in V\) be a point with real algebraic coordinates which is definable by a quantifier free formula involving \(n\) univariate polynomials of degree and logarithmic height at most \(d_1\) and \(M_1\), respectively. Suppose that \(V\) is a real variety definable by equations only. Then the dimension of the Zariski tangent space \(T_x(V)\) of \(V\) at \(x\) can be determined using \(M_1^{O(1)}M^{O(1)}Kd_1^{O(1)}d^{O(n)}\) bit operations (theorem 4.1). Suppose that \(V\) is a semialgebraic set and that the syste…
reviewed by: Joos Heintz
Mathematics Subject Classification ID: 14P10
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 14Q20
zbMATH DE Number: 1330757
zbMATH Keywords: semialgebraic set
zbMATH Keywords: semialgebraic variety
zbMATH Keywords: global dimension
zbMATH Keywords: local dimension
zbMATH Keywords: stratification
zbMATH Keywords: complexity
zbMATH Keywords: quantifier free formula
author: Nicolai Vorobjov
MaRDI profile type: Publication
full work available at URL: jsco.1999.0282
OpenAlex ID: W2002314756
cites work: Q4372496
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q3770650
cites work: Q5184990
cites work: Polynomial-time computation of the dimension of algebraic varieties in zero-characteristic
cites work: Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic
cites work: Q4023642
cites work: Q4850731
cites work: Q4039743
cites work: Q5184991
cites work: Complexity of deciding Tarski algebra
cites work: Solving systems of polynomial inequalities in subexponential time
cites work: Sur la complexité du principe de Tarski-Seidenberg
cites work: The complexity of stratification computation
cites work: Q1185456
cites work: Q4771357
cites work: Q4542567
DOI: 10.1006/JSCO.1999.0282
Recommended article: Q4542567
Recommended article: Q5460918
Recommended article: The complexity of local dimensions for constructible sets
Recommended article: Q4232468
Recommended article: Complexity of finding irreducible components of a semialgebraic set
Recommended article: On Computational Complexity of Semilinear Varieties
Recommended article: On the scale of local computability potentials of algebras
Recommended article: Q4815752
Recommended article: A measure for semialgebraic sets related to Boolean complexity
Recommended article: Q4807964
description: scientific article; zbMATH DE number 1330757