The Computational Complexity of Subalgebra Membership

The problem of deciding and certifying membership in polynomial ideals is of fundamental importance in Computer Algebra and its applications. The complexity of this and the related problem of Gröbner basis computation has been studied (at least) since the 80s, with scary "doubly-exponential" worst-case examples by Mayr & Meyer.

The similar problem of membership in subalgebras of the polynomial ring is in some way (and with many caveats) parallel to that of ideal membership, with SAGBI bases playing the role of Gröbner bases. We investigate the computational complexity of this problem for general, homogeneous, monomial and univariate subalgebras and compare it to the ideal situation.

This is work in progress.