RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2004 Volume 316, Pages 42–54 (Mi znsl725)

This article is cited in 5 papers

Computing the dimension of a semi-algebraic set

S. Basua, R. Pollackb, M.-F. Royc

a School of Mathematics, Georgia Institute of Technology
b Courant Institute of Mathematical Sciences
c University of Rennes 1

Abstract: 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.

UDC: 510.52+512.7

Received: 17.10.2004

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2006, 134:5, 2346–2353

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024