License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.13
URN: urn:nbn:de:0030-drops-126829
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12682/
Bharathi, Arpitha P. ;
Mastrolilli, Monaldo
Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain
Abstract
The Ideal Membership Problem (IMP) asks if an input polynomial f ∈ ?[x₁,… ,x_n] with coefficients from a field ? belongs to an input ideal I ⊆ ?[x₁,… ,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). Our main interest is in understanding when the inherent combinatorial structure of the ideals makes the IMP_d "hard" (NP-hard) or "easy" (polynomial time) to solve.
Such a dichotomy result between "hard" and "easy" IMPs was recently achieved for Constraint Satisfaction Problems over finite domains [Andrei A. Bulatov, 2017; Dmitriy Zhuk, 2017] (this is equivalent to IMP₀) 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, each polymorphism determined the complexity of the computation of a suitable Gröbner basis.
In this paper we consider a 3-element domain and a majority polymorphism (constraints under this polymorphism are a generalisation of the 2-SAT problem). By using properties of the majority polymorphism and assuming graded lexicographic ordering of monomials, we show that the reduced Gröbner basis of ideals whose varieties are closed under the majority polymorphism can be computed in polynomial time. This proves polynomial time solvability of the IMP_d for these constrained problems. We conjecture that this result can be extended to a general finite domain of size k = O(1). This is a first step towards the long term and challenging goal of generalizing the dichotomy results of solvability of the IMP_d for a finite domain.
BibTeX - Entry
@InProceedings{bharathi_et_al:LIPIcs:2020:12682,
author = {Arpitha P. Bharathi and Monaldo Mastrolilli},
title = {{Ideal Membership Problem and a Majority Polymorphism over the Ternary Domain}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {13:1--13:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-159-7},
ISSN = {1868-8969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12682},
URN = {urn:nbn:de:0030-drops-126829},
doi = {10.4230/LIPIcs.MFCS.2020.13},
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: |
|
45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
18.08.2020 |
