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.STACS.2022.18
URN: urn:nbn:de:0030-drops-158280
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15828/
Bulatov, Andrei A. ;
Rafiey, Akbar
The Ideal Membership Problem and Abelian Groups
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.
BibTeX - Entry
@InProceedings{bulatov_et_al:LIPIcs.STACS.2022.18,
author = {Bulatov, Andrei A. and Rafiey, Akbar},
title = {{The Ideal Membership Problem and Abelian Groups}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {18:1--18:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15828},
URN = {urn:nbn:de:0030-drops-158280},
doi = {10.4230/LIPIcs.STACS.2022.18},
annote = {Keywords: Polynomial Ideal Membership, Constraint Satisfaction Problems, Polymorphisms, Gr\"{o}bner Bases, Abelian Groups}
}
|
Keywords: |
|
Polynomial Ideal Membership, Constraint Satisfaction Problems, Polymorphisms, Gröbner Bases, Abelian Groups |
|
Collection: |
|
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
09.03.2022 |
