Geodesic
Computing the dimension of a semi-algebraic set
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 42-54 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of $\mathbf{R}^k$, where $\mathbf{R}$ is a real closed field. We prove that the dimension, $k'$, of a semi-algebraic set described by $s$ polynomials of degree $d$ in $k$ variables can be computed in time $$ \begin{cases} s^{(k-k')k'}d^{O(k'(k-k'))},&\text{if}\ k'\geqslant k/2,\\ s^{(k-k'+1)(k'+1)}d^{O(k'(k-k'))},&\text{if}\ k'< k/2. \end{cases} $$ This result improves slightly the result proved in [22], where an algorithm with complexity bound $(sd)^{O(k'(k-k'))}$ is described for the same problem. The complexity bound of the algorithm described in this paper has a better dependence on the number, $s$, of polynomials in the input. 
@article{ZNSL_2004_316_a2,
     author = {S. Basu and R. Pollack and M.-F. Roy},
     title = {Computing the dimension of a~semi-algebraic set},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {42--54},
     year = {2004},
     volume = {316},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a2/}
}
TY  - JOUR
AU  - S. Basu
AU  - R. Pollack
AU  - M.-F. Roy
TI  - Computing the dimension of a semi-algebraic set
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2004
SP  - 42
EP  - 54
VL  - 316
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a2/
LA  - en
ID  - ZNSL_2004_316_a2
ER  - 
%0 Journal Article
%A S. Basu
%A R. Pollack
%A M.-F. Roy
%T Computing the dimension of a semi-algebraic set
%J Zapiski Nauchnykh Seminarov POMI
%D 2004
%P 42-54
%V 316
%U http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a2/
%G en
%F ZNSL_2004_316_a2
S. Basu; R. Pollack; M.-F. Roy. Computing the dimension of a semi-algebraic set. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part IX, Tome 316 (2004), pp. 42-54. http://geodesic.mathdoc.fr/item/ZNSL_2004_316_a2/

[1] S. Basu, “On Bounding the Betti Numbers and Computing the Euler Characteristics of Semi-algebraic Sets”, Discrete and Computational Geometry, 22 (1999), 1–18 | DOI | MR | Zbl

[2] S. Basu, R. Pollack, M.-F. Roy, “On the Combinatorial and Algebraic Complexity of Quantifier Elimination”, J. of the ACM, 43 (1996), 1002–1045 | DOI | MR | Zbl

[3] S. Basu, R. Pollack, M.-F. Roy, “On Computing a Set of Points meeting every Semi-algebraically Connected Component of a Family of Polynomials on a Variety”, J. of Complexity, 13:1 (1997), 28–37 | DOI | MR | Zbl

[4] S. Basu, R. Pollack, M.-F. Roy, “Computing Roadmaps of Semi-algebraic Sets on a Variety”, J. of the AMS, 3:1 (1999), 55–82 | MR

[5] S. Basu, R. M.-F. Roy, Algorithms in Real Algebraic Geometry, Springer-Verlag, 2003 | MR

[6] J. Canny, The Complexity of Robot Motion Planning, MIT Press, 1987 | MR

[7] J. Canny, “Some Algebraic and Geometric Computations in PSPACE”, Proceedings of the Twentieth ACM Symposium on Theory of Computing, 1988, 460–467

[8] J. Canny, “Computing road maps in general semi-algebraic sets”, The Computer Journal, 36 (1993), 504–514 | DOI | MR | Zbl

[9] J. Canny, D. Grigor'ev, N. Vorobjov, “Finding connected components of a semi-algebraic set in subexponential time”, Appl. Algebra Eng. Commun. Comput., 2:4 (1992), 217–238 | DOI | MR | Zbl

[10] A. Chistov, “Polynomial time computation of the dimension of algebraic varieties in zero characteristic”, J. of Symbolic Computation, 22 (1996), 1–25 | DOI | MR | Zbl

[11] A. Chistov, H. Fournier, L. Gurvits, P. Koiran, “Vandermonde Matrices, NP-Completeness and Trasversal Subspaces”, Foundations of Computational Mathematics, 3:4 (2003), 421–427 | DOI | MR | Zbl

[12] G. Collins, “Quantifier elimination for real closed fields by cylindric algebraic decomposition”, Second GI Conference on Automata Theory and Formal Languages, Lect. Notes Comp. Sci., 33, Springer-Verlag, Berlin, 1975, 134–183 | MR

[13] L. Gournay, J. J. Risler, “Construction of roadmaps of semi-algebraic sets”, Appl. Algebra Eng. Commun. Comput., 4:4 (1993), 239–252 | DOI | MR | Zbl

[14] D. Grigor'ev, “The Complexity of deciding Tarski algebra”, J. of Symbolic Computation, 5 (1988), 65–108 | DOI | MR

[15] D. Grigor'ev, N. Vorobjov, “Solving Systems of Polynomial Inequalities in Subexponential Time”, J. of Symbolic Computation, 5 (1988), 37–64 | DOI | MR

[16] D. Grigor'ev, N. Vorobjov, “Counting connected components of a semi-algebraic set in subexponential time”, Comput. Complexity, 2:2 (1992), 133–186 | DOI | MR

[17] J. Heintz, M.-F. Roy, P. Solernò, “Sur la complexité du principe de Tarski-Seidenberg”, Bull. Soc. Math. France, 118 (1990), 101–126 | MR | Zbl

[18] J. Heintz, M.-F. Roy, P. Solernò, “Single exponential path finding in semi-algebraic sets. II: The general case”, Algebraic geometry and its applications. Collections of papers from Shreeram S., Abhyankar's 60th birthday conference (Purdue University, West Lafayette, IN, USA, June 1–4, 1990), ed. Bajaj, Chandrajit L., Springer-Verlag, New York, 1994, 449–465 | MR | Zbl

[19] J. Heintz, M.-F. Roy, P. Solernò, “Description of the Connected Components of a Semialgebraic Set in Single Exponential Time”, Discrete and Computational Geometry, 11 (1994), 121–140 | DOI | MR | Zbl

[20] P. Koiran, “The real dimension problem is $\mathrm{NP}_{\mathbb R}$-complete”, J. of Complexity, 15 (1997), 227–238 | DOI | MR

[21] J. Renegar, “On the computational complexity and geometry of the first order theory of the reals”, J. of Symbolic Comput., 13 (1992), 255–352 | DOI | MR

[22] N. Vorobjov, “Complexity of computing the dimension of a semi-algebraic set”, J. of Symbolic Comput., 27 (1999), 565–579 | DOI | MR | Zbl