On the intrinsic complexity of elimination theory (Q1330148)

The paper starts with an overview of the known upper bounds for the sequential and parallel time complexity of various algorithmic problems in classical elimination theory. The problems discussed there are the decision and representation version of the ideal triviality and the radical membership problem, as well as the zero- and the general case of the elimination problem. These problems can be solved by well- parallelizable randomized polynomial time algorithms, if the input polynomials are given in dense representation and the output polynomials are coded by straight-line programs. In the second part of the paper the question is raised, whether it is possible to obtain polynomial sequential time algorithms for the above problems, when the input polynomials are given by straight-line programs or in sparse representation. The authors destroy the hope for finding such algorithms by establishing reductions to NP- and \(\text{P}^\#\)- complete problems. Finally, an elimination problem with provably exponential output is presented. The proof of this result is based on a variant of a theorem by Heintz and Sieveking, which provides lower bounds on the complexity of polynomials with algebraic coefficients.