Membership problem, Representation problem and the Computation of the Radical for one-dimensional Ideals

In this paper we consider membership problem, representation problem and also the computation of the radical for one-dimensional ideals in the polynomial ring k[X₁,…, X _n ] from a complexity point of view. Our aim is to give bounds for the complexity of the above problems which are simply exponential in the number n of variables in the one-dimensional case. Moreover we show that in the general case the first two problems are doubly exponential only in the dimension of the ideal, and parallelizable. Many authors considered membership problem (i.e. given polynomials F, F₁,…, F, ∈ k[X₁,…, X _n ], decide whether F belongs to I:= (F1…, F,)) and representation problem (compute a representation A _i ∈ k[X₁,…, X _n ]) from this effective approach. In particular [18] gives a lower bound, doubly exponential in (a fraction of) the numbers of variables n. On the other hand, [4] shows that in “good” cases, for instance for unmixed ideals, the membership problem is simply exponential in n.