Intrinsic Complexity for Constructing Zero-Dimensional Gröbner Bases

In this paper, we give a thorough revision of Lakshman’s paper by fixing some serious flaws in his approach. Furthermore, following this analysis, an intrinsic complexity bound for the construction of zero-dimensional Grobner bases is given. Our complexity bound is in terms of the degree of the input ideal as well as the degrees of its generators. Finally, as an application of the presented method, we exhibit and analyze a (Monte Carlo) probabilistic algorithm to compute the degree of an equidimensional ideal.