×

The determination of isolated points and of the dimension of an algebraic variety can be done in polynomial time. (La détermination des points isolés et de la dimension d’une variété algébrique peut se faire en temps polynomial.) (French) Zbl 0829.14029

Eisenbud, David (ed.) et al., Computational algebraic geometry and commutative algebra. Proceedings of a conference held at Cortona, Italy, June 17-21, 1991. Cambridge: Cambridge University Press. Symp. Math. 34, 216-256 (1993).
Summary: We show that the dimension of an algebraic (affine or projective) variety can be computed by a well parallelizable arithmetical network in nonuniform polynomial sequential time in the size of the input. This input is given by a system of polynomial equations written in dense representation. The coordinates of the ambient space can be put in Noether position with respect to the variety within the same time bounds. – By the way, we consider as an intermediate problem the determination of the isolated points of the given variety, which is of obvious practical interest.
We suppose that the base domain, from where the coefficients of the input polynomials are taken, is infinite and, in the case of an affine variety, that its field of fractions is perfect. If this domain consists of the integers, our algorithms can be realized by boolean networks of the same complexity type (however these networks are not uniform with respect to the number of variables occurring in the input polynomials). Our results imply an effective version of the affine Nullstellensatz in terms of degrees and straight line programs.
For the entire collection see [Zbl 0819.00017].

MSC:

14Q15 Computational aspects of higher-dimensional varieties
68W30 Symbolic computation and algebraic computation
14A05 Relevant commutative algebra
PDFBibTeX XMLCite