Document Open Access Logo

The Ideal Membership Problem and Abelian Groups

Authors Andrei A. Bulatov , Akbar Rafiey

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.18.pdf
  • Filesize: 0.87 MB
  • 16 pages

Document Identifiers

Author Details

Andrei A. Bulatov
  • School of Computing Science, Simon Fraser University, Burnaby, Canada
Akbar Rafiey
  • School of Computing Science, Simon Fraser University, Burnaby, Canada

Funding

  • Bulatov, Andrei A.: Research supported by an NSERC Discovery Grant.
  • Rafiey, Akbar: Research supported by NSERC.

Cite AsGet BibTex

Andrei A. Bulatov and Akbar Rafiey. The Ideal Membership Problem and Abelian Groups. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.18

Abstract

Given polynomials f_0, f_1, …, f_k the Ideal Membership Problem, IMP for short, asks if f₀ belongs to the ideal generated by f_1, …, f_k. In the search version of this problem the task is to find a proof of this fact. The IMP is a well-known fundamental problem with numerous applications, for instance, it underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. Although the IMP is in general intractable, in many important cases it can be efficiently solved. Mastrolilli [SODA'19] initiated a systematic study of IMPs for ideals arising from Constraint Satisfaction Problems (CSPs), parameterized by constraint languages, denoted IMP(Γ). The ultimate goal of this line of research is to classify all such IMPs accordingly to their complexity. Mastrolilli achieved this goal for IMPs arising from CSP(Γ) where Γ is a Boolean constraint language, while Bulatov and Rafiey [arXiv'21] advanced these results to several cases of CSPs over finite domains. In this paper we consider IMPs arising from CSPs over "affine" constraint languages, in which constraints are subgroups (or their cosets) of direct products of Abelian groups. This kind of CSPs include systems of linear equations and are considered one of the most important types of tractable CSPs. Some special cases of the problem have been considered before by Bharathi and Mastrolilli [MFCS'21] for linear equation modulo 2, and by Bulatov and Rafiey [arXiv'21] to systems of linear equations over GF(p), p prime. Here we prove that if Γ is an affine constraint language then IMP(Γ) is solvable in polynomial time assuming the input polynomial has bounded degree.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
  • Mathematics of computing → Gröbner bases and other special bases
Keywords
  • Polynomial Ideal Membership
  • Constraint Satisfaction Problems
  • Polymorphisms
  • Gröbner Bases
  • Abelian Groups

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Albert Atserias and Joanna Ochremiak. Proof complexity meets algebra. ACM Trans. Comput. Log., 20(1):1:1-1:46, 2019. Google Scholar
  2. Libor Barto and Marcin Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61(1):3:1-3:19, 2014. Google Scholar
  3. Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  4. Paul Beame, Russell Impagliazzo, Jan Krajícek, Toniann Pitassi, and Pavel Pudlák. Lower bound on hilbert’s nullstellensatz and propositional proofs. In 35th Annual Symposium on Foundations of Computer Science, FOCS 1994, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 794-806. IEEE Computer Society, 1994. URL: https://doi.org/10.1109/SFCS.1994.365714.
  5. Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal membership problem and a majority polymorphism over the ternary domain. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 13:1-13:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.13.
  6. Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal membership problem for boolean minority. CoRR, abs/2006.16422, 2020. URL: http://arxiv.org/abs/2006.16422.
  7. Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal membership problem for boolean minority and dual discriminator. In 46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021, August 23-27, 2021, Tallinn, Estonia. To appear, 2021. Google Scholar
  8. V.G. Bodnarchuk, L.A. Kaluzhnin, V.N. Kotov, and B.A. Romov. Galois theory for post algebras. i. Kibernetika, 3:1-10, 1969. Google Scholar
  9. Bruno Buchberger. Bruno buchberger’s phd thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Journal of Symbolic Computation, 41(3):475-511, 2006. Logic, Mathematics and Computer Science: Interactions in honor of Bruno Buchberger (60th birthday). URL: https://doi.org/10.1016/j.jsc.2005.09.007.
  10. Andrei A. Bulatov. A dichotomy theorem for nonuniform csps. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330. IEEE Computer Society, 2017. Google Scholar
  11. Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for mal'tsev constraints. SIAM J. Comput., 36(1):16-27, 2006. Google Scholar
  12. Andrei A. Bulatov and Peter Jeavons. An algebraic approach to multi-sorted constraints. In Principles and Practice of Constraint Programming - CP 2003, 9th International Conference, CP 2003, Kinsale, Ireland, September 29 - October 3, 2003, Proceedings, volume 2833 of Lecture Notes in Computer Science, pages 183-198. Springer, 2003. URL: https://doi.org/10.1007/978-3-540-45193-8_13.
  13. Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. URL: https://doi.org/10.1137/S0097539700376676.
  14. Andrei A. Bulatov, Andrei A. Krokhin, and Benoît Larose. Dualities for constraint satisfaction problems. In Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors, Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], volume 5250 of Lecture Notes in Computer Science, pages 93-124. Springer, 2008. Google Scholar
  15. Andrei A. Bulatov and Akbar Rafiey. On the complexity of csp-based ideal membership problems. CoRR, abs/2011.03700, 2020. Google Scholar
  16. Andrei A. Bulatov and Akbar Rafiey. The ideal membership problem and abelian groups. CoRR, abs/2201.05218, 2022. Google Scholar
  17. Samuel R. Buss and Toniann Pitassi. Good degree bounds on nullstellensatz refutations of the induction principle. In Steven Homer and Jin-Yi Cai, editors, Proceedings of the 11th Annual IEEE Conference on Computational Complexity, CCC 1996, Philadelphia, Pennsylvania, USA, May 24-27, 1996, pages 233-242. IEEE Computer Society, 1996. URL: https://doi.org/10.1109/CCC.1996.507685.
  18. Matthew Clegg, Jeff Edmonds, and Russell Impagliazzo. Using the groebner basis algorithm to find proofs of unsatisfiability. In Gary L. Miller, editor, Proceedings of the 28th Annual ACM Symposium on the Theory of Computing, STOC 1996, Philadelphia, Pennsylvania, USA, May 22-24, 1996, pages 174-183. ACM, 1996. URL: https://doi.org/10.1145/237814.237860.
  19. David Cox, John Little, and Donal OShea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2013. Google Scholar
  20. Alicia Dickenstein, Noaï Fitchas, Marc Giusti, and Carmen Sessa. The membership problem for unmixed polynomial ideals is solvable in single exponential time. Discret. Appl. Math., 33(1-3):73-94, 1991. URL: https://doi.org/10.1016/0166-218X(91)90109-A.
  21. D. Geiger. Closed systems of function and predicates. Pacific Journal of Mathematics, pages 95-100, 1968. Google Scholar
  22. Dima Grigoriev. Tseitin’s tautologies and lower bounds for nullstellensatz proofs. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, November 8-11, 1998, Palo Alto, California, USA, pages 648-652. IEEE Computer Society, 1998. URL: https://doi.org/10.1109/SFCS.1998.743515.
  23. Grete Hermann. Die frage der endlich vielen schritte in der theorie der polynomideale. Mathematische Annalen, 95(1):736-788, 1926. Google Scholar
  24. Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput., 39(7):3023-3037, 2010. Google Scholar
  25. Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. URL: https://doi.org/10.1145/263867.263489.
  26. Christopher Jefferson, Peter Jeavons, Martin J. Green, and M. R. C. van Dongen. Representing and solving finite-domain constraint problems using systems of polynomials. Annals of Mathematics and Artificial Intelligence, 67(3):359-382, March 2013. URL: https://doi.org/10.1007/s10472-013-9365-7.
  27. Monaldo Mastrolilli. The complexity of the ideal membership problem for constrained problems over the boolean domain. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 456-475, 2019. URL: https://doi.org/10.1137/1.9781611975482.29.
  28. Ernst W. Mayr. Membership in plynomial ideals over Q is exponential space complete. In Burkhard Monien and Robert Cori, editors, 6th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1989, Paderborn, FRG, February 16-18, 1989, Proceedings, volume 349 of Lecture Notes in Computer Science, pages 400-406. Springer, 1989. URL: https://doi.org/10.1007/BFb0029002.
  29. Ernst W Mayr and Albert R Meyer. The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in mathematics, 46(3):305-329, 1982. Google Scholar
  30. Ryan O'Donnell. SOS is not obviously automatizable, even approximately. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 59:1-59:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.59.
  31. Prasad Raghavendra and Benjamin Weitz. On the bit complexity of sum-of-squares proofs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 80:1-80:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.80.
  32. Fred Richman. Constructive aspects of noetherian rings. Proceedings of the American Mathematical Society, 44(2):436-441, 1974. Google Scholar
  33. Abraham Seidenberg. Constructions in algebra. Transactions of the American Mathematical Society, 197:273-313, 1974. Google Scholar
  34. Johan Thapper and Stanislav Zivný. The limits of SDP relaxations for general-valued csps. ACM Trans. Comput. Theory, 10(3):12:1-12:22, 2018. Google Scholar
  35. Dmitriy Zhuk. A proof of CSP dichotomy conjecture. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331-342. IEEE Computer Society, 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact