Abstract. We consider the polynomial ideal membership problem (IMP) for ideals encoding combinatorial problems that are instances of constraint satisfaction problems over a finite language. In this paper, the input polynomial [Formula: see text] has degree at most [Formula: see text] (we call this problem IMP[Formula: see text]). We bridge the gap in [M. Mastrolilli, The complexity of the ideal membership problem for constrained problems over the Boolean domain, in SODA ’19, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, Society for Industrial and Applied Mathematics, 2019, pp. 456–475] by proving that the IMP[Formula: see text] 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 [Formula: see text]. We also prove that the proof of membership for the [Formula: see text] 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.

In this paper we examine polynomial ideals that are the vanishing ideals of solution sets of combinatorial problems encoded by constraint satisfaction problems over a finite language. We consider a 3-element domain and the dual discriminator polymorphism (constraints under this polymorphism are a generalization of the 2-satisfiability problem). Assuming the graded lexicographic ordering of monomials, we show that the reduced Gröbner basis of ideals whose varieties are closed under this polymorphism can be computed in polynomial time. This proves polynomial time solvability of the ideal membership problem (IMP) with restrictions on degree $d=O(1)$, which we call IMP$_d$, for these constrained problems. It is a first step toward the challenging long-term goal of identifying when IMP$_d$ is polynomial time solvable for a finite domain.

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.

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.