Given a monomial ideal I={m_1,m_2,...,m_k} where m_i
are monomials and a polynomial f as an arithmetic circuit the
Ideal Membership Problem is to test if f in I. We study
this problem and show the following results.
1. If the ideal I={m_1,m_2,....,m_k} for a
constant k then there is a randomized polynomial-time
membership algorithm to test if f is in I. This result holds even for f given by a black-box, when f is of small degree.
2. When I={m_1,m_2,.....m_k} for a constant
k and f is computed by a Sigma Pi Sigma circuit with output
gate of bounded fanin we can test whether f is in I in
deterministic polynomial time. This generalizes the Kayal-Saxena
result (KS07) of deterministic polynomial-time identity testing
for Sigma Pi Sigma circuits with bounded fanin output gate.
3. When k is not constant the problem is coNP-hard. However,
the problem is upper bounded by coAM^{PP} over the field of
rationals, and by coNP^{ModpP} over finite fields.
4. Finally, we discuss identity testing for certain restricted
depth 4 arithmetic circuits.
For ideals I={f_1,....,f_l where each
f_i is in F[x_1,....,x_k] is an arbitrary polynomial but k is a
constant, we show similar results as (a) and (b) above.
Given a monomial ideal I={m_1,m_2,...,m_k} where m_i
are monomials and a polynomial f as an arithmetic circuit the
Ideal Membership Problem is to test if f in I. We study
this problem and show the following results.
1. If the ideal I={m_1,m_2,....,m_k} for a
constant k then there is a randomized polynomial-time
membership algorithm to test if f is in I. This result holds even for
f given by a black-box, when f is of small degree.
2. When I={m_1,m_2,.....m_k} for a constant
k and f is computed by a Sigma Pi Sigma circuit with output
gate of bounded fanin we can test whether f is in I in
deterministic polynomial time. This generalizes the Kayal-Saxena
result (KS07) of deterministic polynomial-time identity testing
for Sigma Pi Sigma circuits with bounded fanin output gate.
3. When k is not constant the problem is coNP-hard. However,
the problem is upper bounded by coAM^{PP} over the field of
rationals, and by coNP^{ModpP} over finite fields.
4. Finally, we discuss identity testing for certain restricted
depth 4 arithmetic circuits.
For ideals I={f_1,....,f_l where each
f_i is in F[x_1,....,x_k] is an arbitrary polynomial but k is a
constant, we show similar results as (a) and (b) above.
\begin{abstract}
Given a monomial ideal I=\angle{m_1,m_2,\cdots,m_k} where m_i
are monomials and a polynomial f as an arithmetic circuit the
\emph{Ideal Membership Problem } is to test if f\in I. We study
this problem and show the following results.
\begin{itemize}
\item[(a)] If the ideal I=\angle{m_1,m_2,\cdots,m_k} for a
\emph{constant} k then there is a randomized polynomial-time
membership algorithm to test if f\in I. This result holds even for
f given by a black-box, when f is of small degree.