Polynomial-time computation of the dimensions of components of algebraic varieties in zero-characteristic (Q1358904): Difference between revisions

An algorithm is described for the computation of the dimensions of all the irreducible components of an algebraic set over a zero characteristic ground field. The algebraic set is given as the zero set of a family of polynomials of degree \(< d\) in \(n\) variables and the working time of the algorithm is polynomial in the size of the input and \(d^n\). Techniques of real algebraic geometry are used in an essential way, hence the restriction to characteristic \(0\). In finite characteristic the best bound presently known is \(O(d^{n^2})\), and is also due to \textit{A. L. Chistov} [see J. Sov. Math. 34, 1838-1882 (1986); translation from Zap. Nauchn. Semin. Leningrad. Otd. Mat. Inst. Steklova 137, 124-188 (1984; Zbl 0561.12010)].