COMPUTING THE DIMENSION OF A SEMI-ALGEBRAIC SET

    loading  Checking for direct PDF access through Ovid

Abstract

In this paper, we consider the problem of computing the real dimension of a given semi-algebraic subset of Rk, where 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 {s(k −k′)k′ dO(k′(k−k′))} k′ ≥k/2 s(k−k′+1)(k′+1)dO(k′(k′−k′)) if k′

This result slightly improves the result by Vorobjov, who described an algorithm with complexity bound (sd)O(k′(k′k′)) 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. Bibliography: 22 titles.

Related Topics

    loading  Loading Related Articles