License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.16
URN: urn:nbn:de:0030-drops-144560
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14456/
Bharathi, Arpitha P. ;
Mastrolilli, Monaldo
Ideal Membership Problem for Boolean Minority and Dual Discriminator
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.
BibTeX - Entry
@InProceedings{bharathi_et_al:LIPIcs.MFCS.2021.16,
author = {Bharathi, Arpitha P. and Mastrolilli, Monaldo},
title = {{Ideal Membership Problem for Boolean Minority and Dual Discriminator}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {16:1--16:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14456},
URN = {urn:nbn:de:0030-drops-144560},
doi = {10.4230/LIPIcs.MFCS.2021.16},
annote = {Keywords: Polynomial ideal membership, Polymorphisms, Gr\"{o}bner basis theory, Constraint satisfaction problems}
}
|
Keywords: |
|
Polynomial ideal membership, Polymorphisms, Gröbner basis theory, Constraint satisfaction problems |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
