Ideal Membership Problem for Boolean Minority and Dual Discriminator
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917821613604864 |
|---|---|
| author | Bharathi, Arpitha P. Mastrolilli, Monaldo |
| author_facet | Bharathi, Arpitha P. Mastrolilli, Monaldo |
| contents | We consider the polynomial Ideal Membership Problem (IMP) for ideals encoding combinatorial problems that are instances of CSPs over a finite language. In this paper, the input polynomial $f$ has degree at most $d=O(1)$ (we call this problem IMP$_d$). We bridge the gap in \cite{MonaldoMastrolilli2019} 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 tractability for the Boolean IMP$_d$. 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 be found in polynomial time. Our results can be used in applications such as Nullstellensatz and Sum-of-Squares proofs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22102 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Ideal Membership Problem for Boolean Minority and Dual Discriminator Bharathi, Arpitha P. Mastrolilli, Monaldo Data Structures and Algorithms Computational Complexity Computational Geometry We consider the polynomial Ideal Membership Problem (IMP) for ideals encoding combinatorial problems that are instances of CSPs over a finite language. In this paper, the input polynomial $f$ has degree at most $d=O(1)$ (we call this problem IMP$_d$). We bridge the gap in \cite{MonaldoMastrolilli2019} 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 tractability for the Boolean IMP$_d$. 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 be found in polynomial time. Our results can be used in applications such as Nullstellensatz and Sum-of-Squares proofs. |
| title | Ideal Membership Problem for Boolean Minority and Dual Discriminator |
| topic | Data Structures and Algorithms Computational Complexity Computational Geometry |
| url | https://arxiv.org/abs/2410.22102 |