Document Open Access Logo

Ideal Membership Problem for Boolean Minority and Dual Discriminator

Authors Arpitha P. Bharathi, Monaldo Mastrolilli

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.16.pdf
  • Filesize: 0.91 MB
  • 20 pages

Document Identifiers

Author Details

Arpitha P. Bharathi
  • IDSIA-USI, Lugano, Switzerland
Monaldo Mastrolilli
  • IDSIA-SUPSI, Lugano, Switzerland

Funding

This research was supported by the Swiss National Science Foundation project 200020-169022 "Lift and Project Methods for Machine Scheduling Through Theory and Experiments".

Cite As Get BibTex

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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.16

Abstract

The polynomial Ideal Membership Problem (IMP) tests if an input polynomial f ∈ 𝔽[x_1,… ,x_n] with coefficients from a field 𝔽 belongs to a given ideal I ⊆ 𝔽[x_1,… ,x_n]. It is a well-known fundamental problem with many important applications, though notoriously intractable in the general case. In this paper we consider the IMP for polynomial ideals encoding combinatorial problems and where the input polynomial f has degree at most d = O(1) (we call this problem IMP_d). 
A dichotomy result between "hard" (NP-hard) and "easy" (polynomial time) IMPs was achieved for Constraint Satisfaction Problems over finite domains [Andrei A. Bulatov, 2017; Dmitriy Zhuk, 2020] (this is equivalent to IMP_0) and IMP_d for the Boolean domain [Mastrolilli, 2019], both based on the classification of the IMP through functions called polymorphisms. For the latter result, there are only six polymorphisms to be studied in order to achieve a full dichotomy result for the IMP_d. The complexity of the IMP_d for five of these polymorphisms has been solved in [Mastrolilli, 2019] whereas for the ternary minority polymorphism it was incorrectly declared in [Mastrolilli, 2019] to have been resolved by a previous result. In this paper we provide the missing link by proving that the IMP_d for Boolean combinatorial ideals whose constraints are closed under the minority polymorphism can be solved in polynomial time. This completes the identification of the precise borderline of tractability for the IMP_d for constrained problems over the Boolean domain. We also prove that the proof of membership for the IMP_d for problems constrained by the dual discriminator polymorphism over any finite domain can also be found in polynomial time. Bulatov and Rafiey [Andrei A. Bulatov and Akbar Rafiey, 2020] recently proved that the IMP_d for this polymorphism is decidable in polynomial time, without needing a proof of membership. Our result gives a proof of membership and can be used in applications such as Nullstellensatz and Sum-of-Squares proofs.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Gröbner bases and other special bases
  • Mathematics of computing → Combinatoric problems
Keywords
  • Polynomial ideal membership
  • Polymorphisms
  • Gröbner basis theory
  • Constraint satisfaction problems

Metrics

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

Related Versions

References

  1. Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In Andrei Krokhin and Stanislav Zivny, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2017. URL: https://doi.org/10.4230/DFU.Vol7.15301.1.
  2. 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, Santa Fe, New Mexico, USA, 20-22 November 1994, pages 794-806, 1994. Google Scholar
  3. Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain. In Javier Esparza and Daniel Kráľ, editors, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), volume 170 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:13, Dagstuhl, Germany, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.13.
  4. Arpitha P. Bharathi and Monaldo Mastrolilli. Ideal membership problem for boolean minority, 2020. URL: http://arxiv.org/abs/2006.16422.
  5. 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.
  6. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs (best paper award). In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330, 2017. Google Scholar
  7. Andrei A. Bulatov. Constraint satisfaction problems: Complexity and algorithms. ACM SIGLOG News, 5(4):4-24, November 2018. URL: https://doi.org/10.1145/3292048.3292050.
  8. Andrei A. Bulatov and Akbar Rafiey. On the complexity of csp-based ideal membership problems, 2020. URL: http://arxiv.org/abs/2011.03700.
  9. Samuel R. Buss and Toniann Pitassi. Good degree bounds on Nullstellensatz refutations of the induction principle. J. Comput. Syst. Sci., 57(2):162-171, 1998. Google Scholar
  10. Hubie Chen. A rendezvous of logic, complexity, and algebra. ACM Comput. Surv., 42(1):2:1-2:32, December 2009. URL: https://doi.org/10.1145/1592451.1592453.
  11. Martin C. Cooper, David A. Cohen, and Peter G. Jeavons. Characterising tractable constraints. Artificial Intelligence, 65(2):347-361, 1994. URL: https://doi.org/10.1016/0004-3702(94)90021-3.
  12. David A. Cox, John Little, and Donal O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer Publishing Company, Incorporated, 4th edition, 2015. Google Scholar
  13. Jean-Charles Faugère, Patrizia M. Gianni, Daniel Lazard, and Teo Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329-344, 1993. URL: https://doi.org/10.1006/jsco.1993.1051.
  14. Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM), 42(6):1115-1145, 1995. Google Scholar
  15. Dima Grigoriev. Tseitin’s tautologies and lower bounds for Nullstellensatz proofs. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 648-652, 1998. Google Scholar
  16. David Hilbert. Ueber die theorie der algebraischen formen. Mathematische Annalen, 36:473-534, 1890. URL: https://doi.org/10.1007/BF01208503.
  17. David Hilbert. Ueber die vollen invariantensysteme. Mathematische Annalen, 42:313-373, 1893. URL: http://eudml.org/doc/157652.
  18. Peter Jeavons. On the algebraic structure of combinatorial problems. Theoretical Computer Science, 200(1):185-204, 1998. URL: https://doi.org/10.1016/S0304-3975(97)00230-2.
  19. Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. URL: https://doi.org/10.1145/263867.263489.
  20. Monique Laurent. Sums of Squares, Moment Matrices and Optimization Over Polynomials, pages 157-270. Springer, New York, 2009. URL: https://doi.org/10.1007/978-0-387-09686-5_7.
  21. Alan K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99-118, 1977. URL: https://doi.org/10.1016/0004-3702(77)90007-8.
  22. Monaldo Mastrolilli. The complexity of the ideal membership problem and theta bodies for constrained problems over the boolean domain. CoRR, to appear in ACM Transactions on Algorithms, abs/1904.04072, 2019. URL: http://arxiv.org/abs/1904.04072.
  23. Monaldo Mastrolilli. The complexity of the ideal membership problem for constrained problems over the boolean domain. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '19, pages 456-475, Philadelphia, PA, USA, 2019. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=3310435.3310464.
  24. Ernst W. Mayr. Membership in polynomial ideals over q is exponential space complete. In B. Monien and R. Cori, editors, STACS 89, pages 400-406, Berlin, Heidelberg, 1989. Springer Berlin Heidelberg. Google Scholar
  25. 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. URL: https://doi.org/10.1016/0001-8708(82)90048-2.
  26. Ryan O'Donnell. SOS Is Not Obviously Automatizable, Even Approximately. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017), volume 67 of Leibniz International Proceedings in Informatics (LIPIcs), pages 59:1-59:10, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.59.
  27. 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), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 80:1-80:13, Dagstuhl, Germany, 2017. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.80.
  28. Prasad Raghavendra and Benjamin Weitz. On the bit complexity of sum-of-squares proofs. In 44th International Colloquium on Automata, Languages, and Programming, ICALP, Poland, pages 80:1-80:13, 2017. Google Scholar
  29. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC '78, pages 216-226, New York, NY, USA, 1978. ACM. URL: https://doi.org/10.1145/800133.804350.
  30. Amir Shpilka. Recent results on polynomial identity testing. In Alexander Kulikov and Nikolay Vereshchagin, editors, Computer Science - Theory and Applications, pages 397-400, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  31. Ágnes Szendrei. Clones in universal algebra. Les Presses de l'Université de Montréal, 1986. Google Scholar
  32. Marc R.C. van Dongen. Constraints, Varieties, and Algorithms. PhD thesis, Department of Computer Science, University College, Cork, Ireland, 2002. URL: http://csweb.ucc.ie/~dongen/papers/UCC/02/thesis.pdf.
  33. Benjamin Weitz. Polynomial Proof Systems, Effective Derivations, and their Applications in the Sum-of-Squares Hierarchy. PhD thesis, EECS Department, University of California, Berkeley, May 2017. URL: http://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-38.html.
  34. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, 2020. URL: https://doi.org/10.1145/3402029.
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 About DROPS Imprint Privacy Contact