Portal de Periódicos da CAPES

The ideal membership problem and polynomial identity testing

2009; Elsevier BV; Volume: 208; Issue: 4 Linguagem: Inglês

10.1016/j.ic.2009.06.003

1090-2651

V. Arvind, Partha Mukhopadhyay,

Machine Learning and Algorithms

Given a monomial ideal I=〈m1,m2,…,mk〉 where mi are monomials and a polynomial f by an arithmetic circuit, the Ideal Membership Problem is to test if f∈I. We study this problem and show the following results. When the ideal I=〈m1,m2,…,mk〉 for a constant k, we can test whether f∈I in randomized polynomial time. This result holds even for f given by a black-box, when f is of small degree. When I=〈m1,m2,…,mk〉 for a constant kandf is computed by a ΣΠΣ circuit with output gate of bounded fanin, we can test whether f∈I in deterministic polynomial time. This generalizes the Kayal–Saxena result [11] of deterministic polynomial-time identity testing for ΣΠΣ circuits with bounded fanin output gate. When k is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMAPP over the field of rationals, and by coNPModpP over finite fields. Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits. For ideals I=〈f1,…,fℓ〉 where each fi∈F[x1,…,xk] is an arbitrary polynomial but k is a constant, we show similar results as (a) and (b) above.