On the parallel complexity of the polynomial ideal membership problem.
(English. English summary)
J. Complexity 14 (1998), no. 2, 176--189.
Summary: "The complexity of the polynomial ideal membership problem
over arbitrary fields within the framework of arithmetic networks is
investigated. We prove that the parallel complexity of this problem is
single exponential over any infinite field. Our lower bound is obtained
by combining a modification of E. W. Mayr and A. R. Meyer's key
construction [Adv. in Math. 46 (1982), no. 3, 305--329; MR 84g:20099]
with an elementary degree bound."
Reviewed by Ralf Froberg
© Copyright American Mathematical Society 1999, 2000