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 wellknown 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" (NPhard) 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 3element domain and a majority polymorphism (constraints under this polymorphism are a generalisation of the 2SAT 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:113:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12682},
URN = {urn:nbn:de:0030drops126829},
doi = {10.4230/LIPIcs.MFCS.2020.13},
annote = {Keywords: Polynomial ideal membership, Polymorphisms, Gr{\"o}bner basis theory, Constraint satisfaction problems}
}
18.08.2020
Keywords: 

Polynomial ideal membership, Polymorphisms, Gröbner basis theory, Constraint satisfaction problems 
Seminar: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Issue date: 

2020 
Date of publication: 

18.08.2020 