The ideal membership problem and polynomial identity testing

详细信息    查看全文

• 作者：V. Arvind ; Partha Mukhopadhyay
• 关键词：Arithmetic circuits ; Polynomial identity testing ; Ideal membership
• 刊名：Information and Computation
• 出版年：2010
• 出版时间：April 2010
• 年：2010
• 卷：208
• 期：4
• 页码：351-363
• 全文大小：276 K

文摘

Given a monomial ideal I=m₁,m₂,…,m_k where m_i are monomials and a polynomial f by an arithmetic circuit, the Ideal Membership Problem is to test if fI. We study this problem and show the following results.

(a) When the ideal I=m₁,m₂,…,m_k for a constant k, we can test whether fI in randomized polynomial time. This result holds even for f given by a black-box, when f is of small degree.

(b) When I=m₁,m₂,…,m_k for a constant is computed by a ΣΠΣ circuit with output gate of bounded fanin, we can test whether fI in deterministic polynomial time. This generalizes the Kayal–Saxena result [11] of deterministic polynomial-time identity testing for ΣΠΣ circuits with bounded fanin output gate.

(c) When k is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMA^PP over the field of rationals, and by coNP^ModpP over finite fields.

(d) Finally, we discuss identity testing for certain restricted depth 4 arithmetic circuits.

For ideals I=f₁,…,f_ℓ where each f_iF[x₁,…,x_k] is an arbitrary polynomial but k is a constant, we show similar results as (a) and (b) above.