×

The ideal membership problem and polynomial identity testing. (English) Zbl 1190.68027

Summary: Given a monomial ideal \(I=\langle m_1,m_2,\dots,m_k\rangle\) where \(m_i\) are monomials and a polynomial \(f\) by an arithmetic circuit, the Ideal Membership Problem is to test if \(f\in I\). We study this problem and show the following results.
(a) When the ideal \(I=\langle m_1,m_2,\dots,m_k\rangle\) for a constant \(k\), we can test whether \(f\in I\) in randomized polynomial time. This result holds even for \(f\) given by a black box, when \(f\) is of small degree.
(b) When \(I=\langle m_1,m_2,\dots,m_k\rangle\) for a constant \(k\) and \(f\) is computed by a \(\Sigma\Pi\Sigma\) circuit with output gate of bounded fan-in, we can test whether \(f\in I\) in deterministic polynomial time. This generalizes the Kayal-Saxena result of deterministic polynomial-time identity testing for \(\Sigma\Pi\Sigma\) circuits with bounded fan-in output gate.
(c) When \(k\) is not constant the problem is coNP-hard. We also show that the problem is upper bounded by coMA\(^{\text{PP}}\) over the field of rationals, and by coNP\(^{\text{Mod}_p\text{P}}\) over finite fields.
(d) Finally, we discuss identity testing for certain restricted depth-4 arithmetic circuits.
For ideals \(I=\langle f_1,\dots,f_\ell\rangle\) where each \(f_i\in\mathbb F[x_1,\dots,x_k]\) is an arbitrary polynomial but \(k\) is a constant, we show similar results as (a) and (b) above.

MSC:

68Q25 Analysis of algorithms and problem complexity
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Agrawal, M.; Biswas, S., Primality and identity testing via Chinese remaindering, J. ACM, 50, 4, 429-443 (2003) · Zbl 1325.68253
[2] Agrawal, M.; Kayal, N.; Saxena, N., Primes is in P, Ann. Math., 160, 2, 781-793 (2004) · Zbl 1071.11070
[5] Arvind, V.; Mukhopadhyay, Partha, The monomial ideal membership problem and polynomial identity testing, Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), LNCS, vol. 4835 (2007), Springer: Springer Berlin · Zbl 1193.68125
[7] Cox, D.; Little, J.; O’Shea, D., Ideals, Varieties and Algorithms, Undergraduate Text in Mathematics (1992), Springer: Springer Berlin
[9] Hermann, G., Die Frage der endlich viel Schritte in der Theorie der Polynomideale, Math. Ann., 95, 736-788 (1926) · JFM 52.0127.01
[11] Kayal, N.; Saxena, N., Polynomial identity testing for depth 3 circuits, Comput. Complex., 16, 2, 115-138 (2007) · Zbl 1173.94470
[12] Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N., Algebraic methods for interactive proof systems, J. ACM, 39, 4, 859-868 (1992) · Zbl 0799.68097
[13] Lovasz, L., On determinants, matchings, and random algorithms, (Fundamentals of Computation Theory: Proceedings of the Conference on Algebraic, Arithmetic, and Categorical Methods in Computation Theory, vol. 2 (1979), Akademic-Verlag), 565-574
[15] Mayr, E.; Meyer, A., The complexity of word problem for commutative semigroups and polynomial ideals, Adv. Math, 46, 305-329 (1982) · Zbl 0506.03007
[17] Mulmuley, K.; Vazirani, U.; Vazirani, V., Matching is as easy as matrix inversion, (Proceedings of the 19th Annual ACM Conference on Theory of Computing (1987), ACM Press), 345-354 · Zbl 0632.68041
[18] Schwartz, J. T., Fast probabilistic algorithm for verification of polynomial identities, J. ACM, 27, 4, 701-717 (1980) · Zbl 0452.68050
[19] Shamir, A., IP=PSPACE, J. ACM, 39, 4, 869-877 (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.