COMPLEXITY ISSUES IN COMPUTATIONAL ALGEBRA
12:00 noon, Thursday, April 16, 1992
719 Broadway, 12th floor conference room
Abstract
The ideal membership problem for the ring of multivariate
polynomials is a central
problem in Computational Algebra.
Relatively tight computational complexity bounds for
this problem are
known in the case of polynomials with coefficients in a field.
After reviewing these results we give an algorithm, together with an upper
bound on its complexity, for the solution
of the membership problem in the case of polynomials with integer coefficients.
This result is obtained adapting Buchberger's algorithm to the integer case.
As an application, we also provide a more general upper bound on the length of strictly
ascending chain of ideals in the ring $Z[x_1,\ldots,x_n]$ .
Many applications of Computational Algebra, however, do not require the complete solution of the membership problems and alternative approaches are available. In this thesis we survey the method of the characteristic sets, originally introduced by Ritt in the forties and now widely applied, particularly in Elementary Geometry Theorem Proving. We present optimal algorithms for computing a characteristic set with simple-exponential sequential and polynomial parallel time complexities.
We finally present an attempt to generalize some of the constructive methods of
Commutative Algebra to the Algebra of differential polynomials.
Rings of differential polynomials do not resemble
their purely algebraic counterparts:
we prove that there exist non-recursive
differential ideals in $Z\{x\}$ and
hence that, in general, no effective
method can be devised to solve the membership problem in this case.
However special classes of ideals can be algorithmically approached and toward
this goal,
we generalize the concept of H-basis, first introduced by Macaulay for
algebraic ideals, to differential rings.