
\section{Introduction}


\begin{abstract}
The Ideal Membership Problem (IMP) tests if an input polynomial $f\in \mathbb{F}[x_1,\dots,x_n]$ with coefficients from a field $\mathbb{F}$ belongs to a given ideal $I \subseteq \mathbb{F}[x_1,\dots,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) $\textsc{IMP}$s was recently achieved for Constraint Satisfaction Problems over finite domains~\cite{Bulatov17,Zhuk17} (this is equivalent to  $\textsc{IMP}_0$) and $\textsc{IMP}_d$ for the Boolean domain~\cite{MonaldoMastrolilli2019}, both based on the classification of the $\textsc{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 $\textsc{IMP}_d$. The complexity of the $\textsc{IMP}_d$ for five of these polymorphisms has been solved in \cite{MonaldoMastrolilli2019} whereas for the ternary minority polymorphism it was incorrectly declared in \cite{MonaldoMastrolilli2019} to have been resolved by a previous result. As a matter of fact the complexity of the $\textsc{IMP}_d$ for the ternary minority polymorphism is open.

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 is achieved by first showing that a \text{Gr\"{o}bner}  basis can be efficiently computed in the lexicographic order for these ideals. Since this is insufficient for the efficient solvability of the $\textsc{IMP}_d$, we show how this \text{Gr\"{o}bner}  basis can be converted to a $d$-truncated \text{Gr\"{o}bner}  basis in graded lexicographic order in polynomial time which ensures the achievement of the result. This result, along with the results in \cite{MonaldoMastrolilli2019}, completes the identification of the precise borderline of tractability for the $\textsc{IMP}_d$ for constrained problems over the Boolean domain.  

This paper is motivated by the pursuit of understanding the recently raised issue of bit complexity of Sum-of-Squares proofs raised by O'Donnell~\cite{odonnell2017}. Raghavendra and Weitz \cite{raghavendra_weitz2017} show
how the $\textsc{IMP}_d$ tractability for combinatorial ideals implies bounded coefficients in Sum-of-Squares proofs.
\end{abstract}
\section{Introduction}
A polynomial ideal is a subset of the polynomial ring $ \mathbb{F}[x_1,\dots,x_n]$ with two properties: for any two polynomials $f,g$ in the ideal, $f+g$ also belongs to the ideal and so does $hf$ for any polynomial $h$. The Hilbert Basis Theorem \cite{HilbertBasisTheorem} states that every ideal $I$ is finitely generated by a set $F=\{f_1,\dots,f_m\}\subset I$, i.e., any polynomial in $I$ is a polynomial combination of elements from $F$. The polynomial Ideal Membership Problem (IMP) is to find out if a polynomial $f$ belongs to an ideal $I$ or not, given a set of generators of the ideal. 
This fundamental algebraic complexity problem was first pioneered by David Hilbert \cite{Hilbert1893} and has important applications in solving polynomial systems and polynomial identity testing \cite{Cox,PIT}. The IMP is, in general, EXPSPACE-complete and Mayr and Meyer show that the problem for multivariate polynomials over the rationals is solvable in exponential space \cite{Mayr1989,MAYR1982305}. The IMP is intractable (can be decided in single exponential time \cite{Dickenstein1991TheMP}) even when the ideal in question is zero-dimensional (number of common zeros of generators is finite). 


The \emph{vanishing ideal} of a set $S\subseteq \mathbb{F}^n$ is the set of all polynomials in $\mathbb{F}[x_1,\dots,x_n]$ that vanish at every point of $S$. This set of polynomials forms an ideal.
In this paper we consider vanishing ideals of the sets $S$ of feasible solutions that arise from Boolean combinatorial optimization problems. The vanishing ideal of the solution space $S$ is defined as its \emph{combinatorial ideal}.
We consider the IMP for polynomial ideals encoding combinatorial problems.  We call such problems where the input polynomial $f$ has degree at most $d=O(1)$ as IMP$_d$.
The polynomial ideals that arise from combinatorial optimization problems frequently have special properties: these ideals are finite domain and therefore zero-dimensional and radical.
The question of identifying problem restrictions which are sufficient to ensure the $\textsc{IMP}_d$ tractability is important from both a practical and a theoretical viewpoint, and has an immediate application to Sum-of-Squares ($\text{SoS}$) proof systems (or Lasserre relaxations) as explained in the following. 

The $\text{SoS}$ proof system is an increasingly popular tool to solve combinatorial optimization problems. Especially over the last few decades, $\text{SoS}$ has had several applications in continuous and discrete optimization (see, e.g.,~\cite{Laurent2009}). 
It was generally believed that a degree $d$ $\text{SoS}$ proof could be computed (if one existed) via the Ellipsoid algorithm in $n^{O(d)}$ time.
O'Donnell~\cite{odonnell2017}, who initially also believed this, gave a counterexample: a polynomial system and a polynomial which had degree two proofs of non-negativity with coefficients of exponential bit-complexity that forced the Ellipsoid algorithm to take exponential time. O'Donnell~\cite{odonnell2017} raised the open problem to establish useful conditions under which ``small'' $\text{SoS}$ proof can be guaranteed automatically.
A first elegant approach to this question is due to Raghavendra and Weitz~\cite{raghavendra_weitz2017} by providing a \emph{sufficient} condition on a polynomial system  that implies bounded coefficients in $\text{SoS}$ proofs.
In particular, the work of Raghavendra and Weitz \cite{raghavendra_weitz2017} shows
that the $\textsc{IMP}_d$ tractability for combinatorial ideals implies polynomially bounded coefficients in $\text{SoS}$ proofs. Therefore, the $\textsc{IMP}_d$ tractability yields to degree $d$ $\text{SoS}$ proof (if one exists) computation via the Ellipsoid algorithm in $n^{O(d)}$ time.
Hence the following question poses itself: 
Which \emph{restrictions} on combinatorial problems can guarantee an efficient computation of the $\textsc{IMP}_d$?

In this paper we consider restrictions on the so-called \emph{constraint language}, namely a set of relations that is used to form the constraints of the considered combinatorial optimization problem. Each constraint language $\Gamma$ gives rise to a particular polynomial ideal membership problem, denoted $\textsc{IMP}_d(\Gamma)$, and the goal is to describe the complexity of the $\textsc{IMP}_d(\Gamma)$ for all constraint languages~$\Gamma$.
This kind of restrictions on the constraint languages have been successfully applied to study the computational complexity classification (and other algorithmic properties) of the decision version of Constraint Satisfaction Problems ($\textsc{CSP}$) over a fixed constraint language $\Gamma$ on a finite domain, denoted $\textsc{CSP}(\Gamma)$ (see \cref{sec:preliminaries}).
This classification started with the classic dichotomy  result of Schaefer \cite{Schaefer78} for 0/1 $\textsc{CSP}$s, and culminated with the recent papers by Bulatov~\cite{Bulatov17} and Zhuk~\cite{Zhuk17}, settling the long-standing Feder-Vardi dichotomy conjecture for finite domain $\textsc{CSP}$s. We refer to~\cite{2017dfu7} for an excellent survey. Note that $\textsc{CSP}(\Gamma)$ corresponds to the very special case of the $\textsc{IMP}_d(\Gamma)$ with $d=0$, i.e. where we are only interested in testing if the constant polynomial ``$1$'' belongs to the combinatorial ideal (see \cref{sect:idealCSP} for more details on Ideal-CSP correspondence). In this paper we are interested in the problem with $d\geq 1$.

Mastrolilli \cite{MonaldoMastrolilli2019} recently claimed a dichotomy result for the $\textsc{IMP}_d(\Gamma)$ that fully answers the above question for 0/1 combinatorial problems: for any constant $d\geq 1$, the $\textsc{IMP}_d(\Gamma)$ of Boolean combinatorial ideals is either decidable in polynomial time or it is NP-complete. 
Note that the solvability of CSP($\Gamma$) (and therefore of the $\textsc{IMP}_0(\Gamma)$) in the Boolean domain is known to admit a nice dichotomy result~\cite{Schaefer78}: it is solvable in polynomial time if all constraints are closed under one of six polymorphisms (majority, minority, MIN, MAX, constant 0 and constant 1), else it is NP-complete. In \cite{MonaldoMastrolilli2019} it is claimed that the IMP$_d(\Gamma)$ for the Boolean domain also has a nice dichotomy result: it is solvable in polynomial time if all constraints are closed under one of four polymorphisms (majority, minority, MIN, MAX), else it is NP-complete. The complexity of the $\textsc{IMP}_d(\Gamma)$ for five of these polymorphisms has been solved in \cite{MonaldoMastrolilli2019} whereas for the ternary minority polymorphism it was incorrectly declared in~\cite{MonaldoMastrolilli2019} to have been resolved by a previous result. As a matter of fact the complexity of the $\textsc{IMP}_d(\Gamma)$ for the ternary minority polymorphism is open.

In this paper we solve this issue by providing the missing link and therefore establishing the full dichotomy result claimed in \cite{MonaldoMastrolilli2019}. To ensure efficiency of the $\textsc{IMP}_d$, it is sufficient to compute a $d$-truncated \text{Gr\"{o}bner}  basis in the graded lexicographic order (see \cref{def:dTruncated GB,sec:preliminaries,sect:background} for definitions and more details).
This is achieved by first showing that a \text{Gr\"{o}bner}  basis can be efficiently computed in the lexicographic order for the minority polymorphism. Since this is insufficient for the efficient solvability of the $\textsc{IMP}_d$, we show how this \text{Gr\"{o}bner}  basis can be converted to a $d$-truncated \text{Gr\"{o}bner}  basis in the graded lexicographic order in polynomial time. This efficiently solves the IMP$_d$ for combinatorial ideals whose constraints are over a language closed under the minority polymorphism. Together with the results in~\cite{MonaldoMastrolilli2019}, our result allows to complete the answer of the aforementioned question by allowing to identify the precise borderline of tractability of the $\textsc{IMP}_d(\Gamma)$. 

Moreover, we believe the techniques described in this paper can be generalized for a finite domain with prime $p$ elements. The basis of this claim comes from the fact that constraints that are linear equations (mod $p$) are associated with an affine polymorphism \cite{Jeavons_UnifyingFramework1995}. We claim that the $\textsc{IMP}_d$ is tractable for problems that are constrained as linear equations (mod $p$). The details are currently being worked out and will soon be updated in the full version of this paper. 
This is a first step towards the long term and challenging goal of generalizing the dichotomy results of solvability of the $\textsc{IMP}_d$ for finite domains.


\textbf{Structure of the paper:} \cref{sec:preliminaries} contains the basic definitions required for this paper, although a reader unfamiliar with $\textsc{CSP}$s over a constraint language or algebraic geometry and \text{Gr\"{o}bner}  bases is strongly recommended to read the standard literature ~\cite{Chen09,Cox} or \cref{sect:background}.

We concretely state our results in \cref{sec:Our Contributions}. In \cref{sec:GBlex} 
we show that the reduced \text{Gr\"{o}bner}  basis in lexicographic order can be efficiently computed for combinatorial problems constrained under the minority polymorphism.
This is achieved in \cref{sec:GBlex} by first computing a \text{Gr\"{o}bner}  basis in modular arithmetic and then transforming it into a \text{Gr\"{o}bner}  basis $G_1$ in regular arithmetic. However, this \text{Gr\"{o}bner}  basis is in the lexicographic monomial ordering, and does not guarantee the efficient solvability of the $\textsc{IMP}_d$. 
In \cref{sec:conversion} we show how to convert $G_1$ to a $d$-truncated \text{Gr\"{o}bner}  basis $G_2$ in graded lexicographic monomial ordering. We prove that this conversion can be obtained in polynomial time for any fixed $d=O(1)$. A simple example is provided in \cref{sec:example}.

\subsection{Preliminaries}\label{sec:preliminaries} 


Let $D$ denote a finite set (\emph{domain}).
By a $k$-ary \textbf{\emph{relation}} $R$ on a domain $D$ we mean a subset of the $k$-th cartesian power $D^k$; $k$ is said to be the \emph{arity} of the relation. We often use relations and (affine) varieties interchangeably since both essentially represent a set of solutions. A \textbf{\emph{constraint language}} $\Gamma$ over $D$ is a set of relations over $D$. A constraint language is \textbf{\emph{finite}} if it contains finitely many relations, and is \emph{Boolean} if it is over the two-element domain $\{0,1\}$. In this paper, $D$ is the Boolean domain.

  A \emph{\textbf{constraint}} over a constraint language $\Gamma$ is an expression of the form $R(x_1,\ldots, x_k)$ where $R$ is a relation of arity $k$ contained in $\Gamma$, and the $x_i$ are variables. A constraint is satisfied by a mapping $\phi$ defined on the $x_i$ if $(\phi(x_1),\ldots, \phi(x_k))\in R$.

\begin{definition}\label{def:csp}
 The \emph{(nonuniform) \textsc{Constraint Satisfaction Problem} ($\textsc{CSP}$)} associated with language $\Gamma$ over $D$ is the problem $\textsc{CSP}(\Gamma)$ in which: an instance is a triple $ \mathcal{C}=(X,D,C)$ where $X=\{x_1,\ldots,x_n\}$ is a set of $n$ variables and $C$  is a set of constraints over $\Gamma$ with variables from $X$. The goal is to decide whether or not there exists a solution, i.e. a mapping $\phi: X\rightarrow D$ satisfying all of the constraints. We will use $Sol( \mathcal{C})$ to denote the set of solutions of $ \mathcal{C}$.
\end{definition}
Moreover, we follow the algebraic approach to Schaefer's dichotomy result \cite{Schaefer78}  formulated by Jeavons \cite{JEAVONS1998185} where each class of CSPs that are polynomial time solvable is associated with a polymorphism.
\begin{definition}\label{def:polymorph}
An operation $f:D^m \rightarrow D$ is a \textbf{polymorphism} of a relation $R\subseteq D^k$ if for any choice of $m$ tuples from $R$ (allowing repetitions), it holds that the tuple obtained from these $m$ tuples by applying $f$ coordinate-wise is in $R$. If this is the case we also say that $f$ \emph{preserves} $R$, or that $R$ is \emph{invariant} or \emph{closed} with respect to $f$. A polymorphism of a constraint language $\Gamma$ is an operation that is a polymorphism of every $R\in \Gamma$.
\end{definition}


In this paper we deal with the \emph{minority} polymorphism: 
\begin{definition}\label{def:minority}
For a finite domain $D$, a ternary operation $f$ is called a \emph{minority} polymorphism (denoted as \textsf{Minority}) if  $f(a,a,b)=f(a,b,a)=f(b,a,a)=b$ for all $a,b\in D$.  
\end{definition}
Note that there is only one minority polymorphism (\textsf{Minority } in short) for the Boolean domain. 

\begin{example}
Consider relations $R_1=\{(0,0,1),(1,0,0),(0,1,1),(1,1,0)\}$ and $R_2=\{(1,1),(0,1)\}$ associated with language $\Gamma$ over $D=\{0,1\}$. Observe that both $R_1$ and $R_2$ are closed under \textsf{Minority}. Consider the instance $(X=\{x,y,z\},D,C=\{C_1,C_2\})$ where constraint $C_1 = R_1 (x,y,z)$ and $C_2= R_2(x,z)$. The assignment $\phi$ where $\phi(x)=0, \phi(y)= 0, \phi(z)=1$ is a solution to this instance of CSP($\Gamma$). 
\end{example}



For a given instance $\mathcal{C}$ of CSP($\Gamma$), the \textbf{\emph{combinatorial ideal}} $\Ideal{Sol( \mathcal{C})}$ is defined as the vanishing ideal of set $Sol( \mathcal{C})$, (see~\cref{def:ideal} in \cref{sect:background}). We call polynomials of the form $x_i(x_i-1)$ \textit{\textbf{domain polynomials}}, denoted by $dom(x_i)$, and it is easy to see that they belong to $\Ideal{Sol( \mathcal{C})}$ for every $i\in [n]$ as they describe the fact that $Sol( \mathcal{C}) \subseteq D^n$. For a more detailed Ideal-CSP correspondence we refer to \cref{sect:idealCSP}.

\begin{definition}\label{def:IMP}
 The {\emph{\textsc{Ideal Membership Problem}}} associated with language $\Gamma$ is the problem $\textsc{IMP}(\Gamma)$ in which
 the input consists of a polynomial $f\in \mathbb{F}[X]$ and a $\textsc{CSP}(\Gamma)$ instance $ \mathcal{C}=(X,D,C)$. The goal is to decide whether $f$ lies in the combinatorial ideal~$\Ideal{Sol( \mathcal{C})}$. We use $\textsc{IMP}_d(\Gamma)$ to denote $\textsc{IMP}(\Gamma)$ when the input polynomial $f$ has degree at most $d$.
\end{definition}
The \text{Gr\"{o}bner}  basis $G$ of an ideal is a set of generators such that $f\in \GIdeal{G} \iff \reduce{f}{G}=0$, where $\reduce{f}{G}$ denotes the remainder of $f$ divided by $G$  (see~\cite{Cox} or \cref{sect:GBbasics} for more details and notations).
\begin{definition}\label{def:dTruncated GB}
  If $G$ is a \text{Gr\"{o}bner}  basis of an ideal, the \textbf{d-truncated \text{Gr\"{o}bner}  basis} $G'$ of $G$ is defined as
  $$G' = G \cap \mathbb{F}[x_1,x_1,\dots,x_n]_d,$$ where $\mathbb{F}[x_1,x_1,\dots,x_n]_d$ is the set of polynomials of degree less than or equal to $d$.
\end{definition}
It is not necessary to compute  a \text{Gr\"{o}bner}  basis of $\Ideal{Sol(\mathcal{C})}$ in its entirety to solve the $\textsc{IMP}_d$. Since the input polynomial $f$ has degree $d=O(1)$, the only polynomials from $G$ that can possibly divide $f$, in the graded lexicographic order (see \cref{def:lex and grlex} in \cref{sect:GBbasics}), are those that are in $G'$. The remainders of such divisions are also in $\mathbb{F}[x_1,x_1,\dots,x_n]_d$. Therefore, by \cref{th:gbprop,th:imp}, the membership test can be computed by
using only polynomials from $G'$ and therefore we have
$$f \in \Ideal{Sol(\mathcal{C})} \cap \mathbb{F}[x_1,x_1,\dots,x_n]_d \iff \reduce{f}{G'}=0.$$
From the previous observations it follows that if we can compute $G'$ in $n^{O(d)}$ then this yields an algorithm that runs in $n^{O(d)}$ time for the $\textsc{IMP}_d$ (note that the size of the input polynomial $f$ is bounded by $n^{
O(d)}$).

\subsection{Our contributions}\label{sec:Our Contributions}

In this paper we focus on instances $\mathcal{C}=(X=\{x_1,\dots,x_n\},D=\{0,1\},C)$ of CSP($\Gamma$) (see \cref{def:csp}) where $\Gamma$ is a language  that is closed under \textsf{Minority}\  (see \cref{def:minority}). We first produce the reduced \text{Gr\"{o}bner}  basis $G_1$ of $\vb{I}(Sol(\mathcal{C}))$ according to the lexicographic order. Note that this \text{Gr\"{o}bner}  basis does not guarantee finding a solution to the $\textsc{IMP}_d(\Gamma)$ in polynomial time.  
In \cref{sec:conversion} we show how to convert $G_1$ to a $d$-truncated \text{Gr\"{o}bner}  basis $G_2$ for a graded lexicographic monomial ordering. We prove that this computation can be obtained in polynomial time for any fixed $d=O(1)$. As pointed out at the end of \cref{sec:preliminaries}, an efficient computation of $G_2$ yields an efficient algorithm for the $\textsc{IMP}_d$. A simple example is provided in \cref{sec:example}.
Thus we have the following main results:

\begin{theorem}\label{thm:MainTheorem}
The $d$-truncated reduced \text{Gr\"{o}bner}  basis of a Boolean combinatorial ideal whose constraints are closed under the minority polymorphism can be computed in $n^{O(d)}$ time, assuming the graded lexicographic ordering of monomials.
\end{theorem}
This proves the following:
\begin{corollary}\label{cor:MainCorollary}
  The $\textsc{IMP}_d(\Gamma)$, over the Boolean domain, can be solved in polynomial time for $d=O(1)$ if the solution space of every constraint in $\Gamma$ is closed under the minority polymorphism.
\end{corollary}

\emph{Structure of the proof:} A high level description of the proof structure is as follows. Each constraint that is closed under the minority polymorphism can be written in terms of linear equations (mod 2) (see e.g. \cite{Chen09}). In \cref{sec:GBlex}, we first express these equations in their reduced row echelon form: that is to say the `leading variable' (the variable that comes first in the lexicographic order or \textsf{lex } in short, see \cref{def:lex and grlex}) in each equation does not appear in any other (mod 2) equation.
We then show how each polynomial in (mod 2) translates to a polynomial in regular arithmetic with exactly the same 0/1 solutions. The use of elementary symmetric polynomials allows for an efficient computation of the polynomials in regular arithmetic. Using these, we produce a set of polynomials $G_1$ and prove that $G_1$ is the reduced \text{Gr\"{o}bner}  basis of $\vb{I}(Sol(\mathcal{C}))$ in the \textsf{lex } order.
As already mentioned, a \text{Gr\"{o}bner}  basis in the \textsf{lex } order does not guarantee the efficient solvability of the $\textsc{IMP}_d$.
We provide a conversion algorithm in \cref{sec:conversion} which converts $G_1$ to the $d$-truncated reduced \text{Gr\"{o}bner}  basis $G_2$ of $\vb{I}(Sol(\mathcal{C}))$ in the graded lexicographic ordering (\textsf{grlex} for short, see \cref{def:lex and grlex}).
In \cref{sec:ProductOfBooleanFunctions} we show how polynomials in $G_1$ from \cref{sec:GBlex} are handled so our conversion algorithm in \cref{sec:OurAlgorithm} works in polynomial time. \cref{thm:correctness_algorithm} proves the correctness and polynomial running time of the conversion algorithm. This gives the proof of the main results of the paper stated in  \cref{thm:MainTheorem} and \cref{cor:MainCorollary}. 


\section{\text{Gr\"{o}bner}  bases in \textsf{lex } order}\label{sec:GBlex}

Consider an instance $\mathcal{C}=(X=\{x_1,\dots,x_n\},D=\{0,1\},C)$ of CSP($\Gamma$) where $\Gamma$ is a language  that is closed under \textsf{Minority}. Any constraint of $\mathcal{C}$ can be written as a system of linear equations over $\textrm{GF}(2)$ (see e.g. \cite{Chen09}). 
These linear systems with variables $x_1,\dots,x_n$ can be solved by Gaussian elimination. If there is no solution, then we have from Hilbert's Weak Nullstellensatz (\cref{th:nullstz}) that $1\in \vb{I}(Sol(\mathcal{C})) \iff Sol(\mathcal{C})=\emptyset \iff \vb{I}(Sol(\mathcal{C})) = \mathbb{R}[\vb{x}]$. If $1\in \vb{I}(Sol(\mathcal{C}))$ the reduced \text{Gr\"{o}bner}  basis is $\{1\}$. We proceed only if $Sol(\mathcal{C})\neq\emptyset$.
In this section, we assume the \textsf{lex } order $>_\textsf{lex }$ with $x_1>_\textsf{lex } x_2>_\textsf{lex } \dots >_\textsf{lex } x_n$. We also assume that the linear system has $r\leq n$ equations and is already in its reduced row echelon form with $x_i$ as the leading monomial of the $i$-th equation. Let $Supp_i\subset [n]$ such that $\{x_j:j\in Supp_i\}$ is the set of variables appearing in the $i$-th equation of the linear system except for $x_i$. Let the $i$-th equation be $R_i = 0 \Mod{2}$ where 
\begin{equation}\label{eq:Ri}
    R_i := x_i\oplus f_i,     
\end{equation}
with $i\in[r]$ and $f_i$ is the Boolean function $(\bigoplus_{j\in Supp_i} x_j)\oplus \alpha_i$ and $\alpha_i = 0/1$.

\subsection{From (mod 2) to regular arithmetic \text{Gr\"{o}bner}  basis} 
In this section, we show how to transform $R_i$'s into polynomials in regular arithmetic.
The idea is to map $R_i$ to a polynomial $R_i'$ over $\mathbb{R}[x_1, \ldots, x_n]$ such that $a\in \{0,1\}^n$ satisfies $R_i=0$ if and only if $a$ satisfies $R_i' = 0$. Moreover, $R_i$ is such that it has the same leading term as $R_i'$.
We produce a set of polynomials $G_1$ and prove that $G_1$ is the reduced \text{Gr\"{o}bner}  basis of $\vb{I}(Sol(\mathcal{C}))$ over $\mathbb{R}[x_1, \ldots, x_n]$ in the \textsf{lex } ordering.
We define $R'_i$ as
\begin{align}
    R_{i}':= x_i - M(f_i) \label{eq:R'_i}
\end{align}
where
\begin{align}\label{eq:mod2regexpansion}
    M(f_i) &= 
    \begin{cases}
    \sum\limits_{k=1}^{|Supp_i|} \left( (-1)^{k-1}\cdot 2^{k-1}\sum\limits_{\{x_{j_1},\dots,x_{j_k}\}\subseteq Supp_i}x_{j_1}x_{j_2}\cdots x_{j_k}\right) \textrm{ when } \alpha_i=0\\
    1+\sum\limits_{k=1}^{|Supp_i|} \left( (-1)^{k}\cdot 2^{k-1}\sum\limits_{\{x_{j_1},\dots,x_{j_k}\}\subseteq Supp_i}x_{j_1}x_{j_2}\cdots x_{j_k}\right)  \textrm{ when } \alpha_i=1
    \end{cases}
\end{align}

\begin{lemma} Consider the following set of polynomials:
\begin{align}\label{eq:GrobBasisLex}
    G_1=\{R_1',\ldots, R_r',x_{r+1}^2-x_{r+1},\ldots, x_n^2-x_n\},
\end{align}
where $R_i'$ is from \cref{eq:R'_i}. $G_1$ is the reduced \text{Gr\"{o}bner}  basis of $\vb{I}(Sol(\mathcal{C}))$ in the lexicographic order $x_1>_\textsf{lex } x_2>_\textsf{lex } \dots,>_\textsf{lex } x_n$.
\end{lemma}
\begin{proof} For any two Boolean variables $x$ and $y$,
\begin{align}\label{eq:mod2arith}
    x\oplus y &= x+y- 2xy.
\end{align}
By repeatedly using \cref{eq:mod2arith} to obtain the equivalent expression for $f_i$, we see that $R_i=0 \Mod{2}$ and $R_i'=0$ have the same set of 0/1 solutions. Therefore $\Variety{\GIdeal{G_1}}$ is equal to $Sol(\mathcal{C})$. This implies that $\GIdeal{G_1} \subseteq \vb{I}(Sol(\mathcal{C}))$. Moreover, $\textnormal{LM}(R_i)=\textnormal{LM}(R_i')=x_i$, by construction. For every pair of polynomials in $G_1$ the reduced $S$-polynomial is zero as the leading monomials of any two polynomials in $G_1$ are relatively prime. By Buchberger's Criterion (see \cref{th:crit}) it follows that $G_1$ is a \text{Gr\"{o}bner}  basis of $\GIdeal{G_1}$ over $\mathbb{R}[x_1,\ldots,x_n]$ (according to the \textsf{lex } order). In fact, it can be seen by inspection that $G_1$ is the \textit{reduced} \text{Gr\"{o}bner}  basis of $\GIdeal{G_1}$.
To prove that $\vb{I}(Sol(\mathcal{C})) = \GIdeal{G_1}$, we need to prove that any $p \in \vb{I}(Sol(\mathcal{C})) \implies p\in \GIdeal{G_1}$. It is enough to prove that $p|_{G_1} = 0$ as this implies $p\in \GIdeal{G_1}$. We have that $p|_{G_1}$ cannot contain variable $x_i$ for all $1\leq i \leq r$. Hence $p|_{G_1}$ is multilinear in $x_{r+1},x_{r+2},\dots,x_n$.  Each tuple of $D^{n-r}$ extends to exactly that $n-$tuple in $Sol(\mathcal{C})$ whose coordinate associated with $x_i$ ($1\leq i\leq r$) is the unique value $x_i$ takes to satisfy $x_i\oplus f_i = 0$ (see \cref{eq:Ri} and \cref{eq:R'_i}). As $p|_{G_1}$ is multilinear in $x_{r+1},x_{r+2},\dots,x_n$, there are at most $2^{n-r}$ coefficients. Since every point of $D^{n-r}$ is a solution of $p|_{G_1}$, we see that every coefficeint of $p|_{G_1}$ is zero and hence $\reduce{p}{G_1}$ is the zero polynomial. Hence $G_1$ is the reduced \text{Gr\"{o}bner}  basis of $\vb{I}(Sol(\mathcal{C}))$.
\end{proof}







\begin{example}
Consider a system with just one equation with $R_1:= x_1\oplus x_2 \oplus x_3 = 0$ where  $x_1>_\textsf{lex } x_2>_\textsf{lex } x_3$. Then $f_1:= x_2 \oplus x_3$ and $M(f_1):= x_2 + x_3 -2x_2x_3$. The polynomial corresponding to \cref{eq:R'_i} is
\begin{align*}
    R_{1}':= x_1-x_2-x_3+2x_2x_3.
\end{align*}
The equations $R_1=0$ and $R_{1}'=0$ have the same set of 0/1 solutions and  $\textnormal{LM}(R_1)=\textnormal{LM}(R_{1}')=x_1$. For every pair of polynomials in $G=\{R_{1}',x_2^2-x_2,x_3^2-x_3\}$ the reduced $S$-polynomial is zero. By Buchberger's Criterion (see e.g. \cite{Cox} or \cref{th:crit} in the appendix) it follows that $G$ is a \text{Gr\"{o}bner}  basis over $\mathbb{R}[x_1,x_2,x_3]$ (according to the specified \textsf{lex } order). 
\end{example}


Note that the reduced \text{Gr\"{o}bner}  basis in \cref{eq:GrobBasisLex} can be ``efficiently'' computed by exploiting the high degree of symmetry in each $M(f_i)$ and using a version of the elementary symmetric polynomials.


\section{Conversion of basis}\label{sec:conversion}

Now that we have the reduced \text{Gr\"{o}bner}  basis in \textsf{lex } order, we show how to obtain the $d$-truncated reduced \text{Gr\"{o}bner}  basis in \textsf{grlex} order in polynomial time for any fixed $d=O(1)$. Before we describe our conversion algorithm, we show how to expand a product of Boolean functions. This expansion will play a crucial step in our algorithm.   
\subsection{Expansion of a product of Boolean functions}\label{sec:ProductOfBooleanFunctions}
In this section, we show a relation between a product of Boolean functions and (mod 2) sums of the Boolean functions, which is heavily used in our conversion algorithm in \cref{sec:OurAlgorithm}. We have already seen from \cref{eq:mod2arith} that if $f,g$ are two Boolean functions,\footnote{We earlier considered Boolean variables, but the same holds for Boolean functions.}
then 
$$2\cdot f\cdot g = f+g-(f\oplus g).$$

Hence it can be proved by repeated use of the above equation that the following holds for Boolean functions $f_1,$ $f_2,\dots,f_m$:

\begin{equation}\label{eq:mod2expansion}
\begin{aligned}
f_1\cdot f_2 \cdots f_m = \frac{1}{2^{m-1}}\biggl[ &\sum_{i\in[m]} f_i - \sum_{\{i,j\}\subset [m]} (f_i\oplus f_j) + \sum_{\{i,j,k\}\subset [m]} (f_i\oplus f_j \oplus f_k) + \dots +\\ 
&(-1)^{m-1}(f_1\oplus f_2 \oplus \dots \oplus f_m)\biggr].
\end{aligned}
\end{equation}
We call each Boolean function of the form $(f_{i_1}\oplus\cdots\oplus f_{i_k})$ in \cref{eq:mod2expansion} as a \textbf{Boolean term}. We call the Boolean term $(f_1\oplus f_2 \oplus \dots \oplus f_m)$ as the \textbf{longest Boolean term} of the expansion.
Thus, a product of Boolean functions can be expressed as a linear combination of Boolean terms. Note that \cref{eq:mod2expansion} is \textit{symmetric} with respect to $f_1,f_2,\dots,f_m$ as any $f_i$ interchanged with $f_j$ produces the same expression. It is no coincidence that we chose the letter $f$ in the above equation: we later apply this identity using $f_j$ from $R_j:=x_j\oplus f_j$ (see \cref{sec:GBlex}). When we use \cref{eq:mod2expansion} in the conversion algorithm, we will have to evaluate a product of at most $d$ functions, i.e. $m\leq d=O(1)$.
We now see in the right hand side of \cref{eq:mod2expansion} that the coefficient $1/2^{m-1}$ is of constant size and there are $O(1)$ many Boolean terms.

\subsection{Our conversion algorithm}\label{sec:OurAlgorithm}
The FGLM \cite{FAUGERE1993329} conversion algorithm is well known in computer algebra for converting a given reduced \text{Gr\"{o}bner}  basis of a zero dimensional ideal in some ordering to the reduced \text{Gr\"{o}bner}  basis in any other ordering. However, it does so with $O(nD(\langle G_1 \rangle)^3)$ many arithmetic operations, where $D(\GIdeal{G_1})$ is the dimension of the $\mathbb{R}$-vector space $\mathbb{R}[x_1,\dots,x_n]/\GIdeal{G_1}$ (see Proposition 4.1 in \cite{FAUGERE1993329}). $D(\GIdeal{G_1})$ is also equal to the number of common zeros (with multiplicity) of the polynomials from $\GIdeal{G_1}$, which would imply that for the combinatorial ideals considered in this paper, $D(\GIdeal{G_1})=O(2^{n-r})$. This exponential running time is avoided in our conversion algorithm by exploiting the symmetries in \cref{eq:mod2regexpansion} and by truncating the computation up to degree $d$.



Some notations necessary for the algorithm are as follows: $G_1$ and $G_2$ are the reduced \text{Gr\"{o}bner}  basis of $\GIdeal{G_1}$ in \textsf{lex } and \textsf{grlex} ordering respectively. $\textnormal{LM}(G_i)$ is the set of leading monomials of polynomials in $G_i$ for $i\in\{1,2\}$. Since we know $G_1$, we know $\textnormal{LM}(G_1)$, whereas $G_2$ and $\textnormal{LM}(G_2)$ are constructed by the algorithm. $B(G_1)$ is the  set of monomials that cannot be divided (considering the \textsf{lex } order) by any monomial of $\textnormal{LM}(G_1)$. Therefore, $B(G_1)$ is the set of all multilinear monomials in variables $x_{r+1},\dots,x_n$. Similarly, $B(G_2)$ is the set of monomials that cannot by divided (considering the \textsf{grlex} order) by any monomial of $\textnormal{LM}(G_2)$. 

Recall the definition of $f_i$ for $i\leq r$ from \cref{sec:GBlex}. For $i>r$, for notational purposes, we define the Boolean function $f_i:=x_i$.

\begin{lemma}\label{lem:q in Boolean Terms}
Consider a monomial $q$ such that $deg(q)\leq d$. Then $\reduce{q}{G_1}$ can be expressed as a linear combination of Boolean terms.
\end{lemma}
\begin{proof}
Consider $q=x_{i_1}x_{i_2}\cdots x_{i_k}$ where $k\leq d$. Then from \cref{eq:Ri,eq:R'_i}, $\reduce{q}{G_1} = f_{i_1}f_{i_2}\cdots f_{i_k}$ and the lemma holds using \cref{eq:mod2expansion}.
\end{proof}
Let elements $b_i$ of $B(G_2)$ be arranged in increasing \textsf{grlex} order. We construct a set $C$ in our algorithm such that its elements $c_i$ are defined as $c_i=\reduce{b_i}{G_1}$ written as linear combinations of Boolean terms using \cref{lem:q in Boolean Terms}.
We say that a Boolean term $f$ of $c_i$ ``appears in $c_j$'' for some $j<i$ if the longest Boolean term of $c_j$ is $f\oplus\alpha$ where $\alpha=0/1$.\\ 

Let $Q$ be the set of all monomials $m$ such that $1<_\textsf{grlex} deg(m) \leq_\textsf{grlex} d$. We recommend the reader to refer to the example in \cref{sec:example} and \cref{sec:Example in detail} for an intuitive working of the algorithm. We now describe the algorithm in full (we assume $1 \notin \vb{I}(Sol(\mathcal{C}))$, else $G_1=\{1\}=G_2$ and we are done): \\

\noindent \textbf{Inputs:} Degree $d$, $G_1$, $Q$ \\
\textbf{Initial states:} $G_2= \emptyset$, $B(G_2)=\{1(=b_1)\}$, $C=\{1(=c_1)\}$, $q=x_n$.\\
\textbf{Outputs:} $d$-Truncated versions of $G_2$, $B(G_2)$.

\begin{itemize}
    \item \textbf{Main loop:}
    Find ${q}|_{G_1}$, by which we simply replace any occurrence of $x_i$ by the Boolean functions $f_i$. Expand ${q}|_{G_1}$ by using \cref{eq:mod2expansion}. 
    \begin{itemize}
        \item Suppose the longest Boolean term of ${q}|_{G_1}$ does not appear in any $c\in C$. Then ${q}|_{G_1}$ is written as a linear combination of $\reduce{b_i}{G_1}$ and its longest Boolean term (see \cref{lem:C}). This polynomial is added to $C$ and $q$ is added to $B(G_2)$. Go to \textbf{Termination check}.
        \item If the longest Boolean term of ${q}|_{G_1}$ appears in some $c\in C$, then every Boolean term of ${q}|_{G_1}$ can be written as linear combinations of $\reduce{b_j}{G_1}$'s. Note that if the longest Boolean term $f$ appears in $c$ as $f\oplus 1$, then we use $f\oplus 1 = 1- (f)$ (see \cref{eq:mod2arith}). Thus we have ${q}|_{G_1}=\sum_j k_j\reduce{b_j}{G1} \implies q-\sum_j k_jb_j \in \GIdeal{G_1}$. The polynomial $q-\sum_j k_jb_j$ is added to $G_2$ and $q$ to $\textnormal{LM}(G_2)$. Go to \textbf{Termination check}.
    \end{itemize}
    \item \textbf{Termination check:} We delete the occurrence of $q$ from $Q$. If $q$ was added to $\textnormal{LM}(G_2)$ then we delete any monomial in $Q$ that $q$ can divide. The algorithm terminates if $Q$ is empty, else go to \textbf{Next monomial}.
    \item \textbf{Next monomial:} Choose the smallest (according to \textsf{grlex} order) monomial in $Q$ as $q$. Go to \textbf{Main loop}.
\end{itemize}

\begin{lemma}\label{lem:C}
The set $C$ is such that every $c_i$ is a linear combination of existing $\reduce{b_j}{G_1}$'s ($j<i$) and the longest Boolean term of $\reduce{b_i}{G_1}$.
\end{lemma}

\begin{proof}
By definition, element $c_i$ is added to $C$ when a monomial $q$ is added to $B(G_2)$ where $b_i=q$ and $c_i=\reduce{b_i}{G_1}$ expressed in Boolean terms (see Main loop). This means that $q$ is not divisible by any monomial in $\textnormal{LM}(G_2)$. We prove the lemma by induction on the degree of $q$. Note that $b_1 = 1$ and hence $c_1 = \reduce{b_1}{G_1} = 1$.

If $deg(q)=1$, then $q$ is some $x_i$ and $\reduce{x_i}{G_1}$ is one of $0,1$ or $f_i$. If $\reduce{x_i}{G_1}$ is either 0 or 1, then it then appears in $c_1$. We are now in the second case of the Main loop, so $q$ should be added to $\textnormal{LM}(G_2)$ and not $B(G_2)$. Hence $\reduce{x_i}{G_1}$ can be neither 0 nor 1 and the lemma holds for $deg(q)=1$ as $f_i$ is the longest Boolean term.

Let us assume the statement holds true for all monomials with degree less than $m$. Consider $q$ such that $deg(q)=m$ and $q=x_{i_1}x_{i_2}\dots x_{i_m}$ where $i_j$'s need not be distinct, and the lemma holds for every monomial $<_{\textsf{grlex}} q$. Then $\reduce{q}{G_1} = f_{i_1}\cdot f_{i_2}\cdots f_{i_m}$.
Let $(f_{j_1}\oplus \cdots \oplus f_{j_k})$ be a Boolean term in the expansion of $\reduce{q}{G_1}$ (by using \cref{eq:mod2expansion}), that is not the longest Boolean term, so $\{j_1,\dots,j_k\}\subset \{i_1,\dots,i_m\}$ and $k<m$. 
Consider the monomial $x_{j_1}x_{j_2}\dots x_{j_k}$. We will now prove that $x_{j_1}x_{j_2}\dots x_{j_k}$ is in fact some $b_l\in B(G_2)$ and there exists $c_l\in C$ which is a linear combination of $\reduce{b_i}{G_1}$'s and $(f_{j_1}\oplus \cdots \oplus f_{j_k})$.
The monomial $x_{j_1}x_{j_2}\dots x_{j_k}$ either belongs to $LM(G_2)$ or $B(G_2)$.
If $x_{j_1}x_{j_2}\dots x_{j_k}\in\textnormal{LM}(G_2)$ then it divides $q$, a contradiction to our choice of $q$. Therefore, $x_{j_1}x_{j_2}\dots x_{j_k}=b_l\in B(G_2)$.
Clearly $b_l<_{\textsf{grlex}}q$ and the induction hypothesis applies, so there exists $c_l\in C$ such that
$$\reduce{b_l}{G_1}=c_l=\sum_{i < l} a_i\reduce{b_i}{G_1} + a_0(f_{j_1}\oplus \cdots \oplus f_{j_k})$$
where $a_i$'s are constants.
Then we simply use the above equation to substitute for the Boolean term $f_{j_1}\oplus \cdots \oplus f_{j_k}$ in $\reduce{q}{G_1}$ as a linear combination of $\reduce{b_i}{G_1}$ where $i\leq l$. We can do this for every Boolean term of $\reduce{q}{G_1}$ except the longest one. Hence the lemma holds.
\end{proof}




	
	


 



\begin{theorem}\label{thm:correctness_algorithm}
The conversion algorithm terminates for every input $G_1$ and correctly computes a $d$-truncated reduced \text{Gr\"{o}bner}  basis, with the \textsf{grlex} ordering, of the ideal $\GIdeal{G_1}$ in polynomial time.
\end{theorem}
\begin{proof}
The Main loop runs at most $|Q| = O(n^d)$ times. Evaluation of any $\reduce{q}{G_1}$ can be done in $O(n)$ steps (see \cref{eq:mod2expansion}), checking if previous $c_i$'s appear (and replacing every Boolean term appropriately if it does) takes at most $O(n^d)$ steps since there are at most $|Q|$ many elements in $C$. Hence the running time of the algorithm is $O(n^{2d})$.

Suppose the set of polynomials $\{g_1, g_2, \dots, g_k\}$ is the output of the algorithm for some input $G_1$. Clearly, $deg(g_i)\leq d$ for all $i\in [k]$. We now prove by contradiction that the output is the $d$-truncated \text{Gr\"{o}bner}  basis of the ideal $\GIdeal{G_1}$ with the \textsf{grlex} ordering.  Suppose $g$ is a polynomial of the ideal with $deg(g)\leq d$, but no $\textnormal{LM}(g_i)$ can divide $\textnormal{LM}(g)$. In fact, since every $g_i\in \GIdeal{G_1}$ we can replace $g$ by $\reduce{g}{\{g_1, g_2, \dots, g_k\}}$ ($g$ generalises the reduced $S$-polynomial). The fact that $g\in\GIdeal{G_1}$ and $\reduce{g}{G_1}=0$ implies that $\textnormal{LM}(g)$ is a linear combination of monomials that are less than $\textnormal{LM}(g)$ (in the \textsf{grlex} order) and hence must be in $B(G_2)$, i.e 
$$\reduce{g}{G_1}=0 \implies \reduce{\textnormal{LM}(g)}{G_1}=\sum_i k_i\reduce{b_i}{G_1}$$
where every $b_i\in B(G_2)$ and $b_i<_\textsf{grlex} \textnormal{LM}(g)$. When the algorithm runs for $q=\textnormal{LM}(g)$, since $q$ was not added to $\textnormal{LM}(G_2)$,
$$\reduce{\textnormal{LM}(g)}{G_1}= \sum_j k_j\reduce{b_j}{G_1} + f$$
where $f$ is the longest Boolean term of $\reduce{\textnormal{LM}(g)}{G_1}$ which does not appear in any previous element of $C$. But the two equations above imply that $\sum_i k_i\reduce{b_i}{G_1} = \sum_j k_j\reduce{b_j}{G_1} + f$, which proves that there exists some $b_l\in B(G_2)$ such that $c_l$ has $f$ as its longest Boolean term, so $f$ should have appeared in $c_l$, a contradiction. Therefore the output is a $d$-truncated \text{Gr\"{o}bner}  basis. Although unnecessary for the $\textsc{IMP}_d$, we also prove that the output is reduced: every non leading monomial of every polynomial in the output comes from $B(G_2)$ and no leading monomial is a multiple of another by construction (see Termination check).
\end{proof}
Thus we have proof of the main theorem and corollary (see \cref{thm:MainTheorem} and \cref{cor:MainCorollary}).


\section{An example}\label{sec:example}
We provide a simple example in \cref{tab:example} where we convert the reduced \text{Gr\"{o}bner}  basis in \textsf{lex } order of a combinatorial ideal to one in \textsf{grlex} order. Consider the problem formulated by the following (mod 2) equations: $x_1 \oplus x_3 \oplus x_4 = 0$ and $x_2 \oplus x_3 \oplus x_5 \oplus 1 = 0$. The example is explained in more detail in \cref{sec:Example in detail}.

\begin{table}[ht]
    \centering
    \begin{tabular}{c|c|c|c|c}
    \#  &  $q$ & $B(G_2)$ & $C$ & $G_2$\\
    \hline
    0 &  -  & 1 & $1$ & $\emptyset$ \\
    1 & $x_5$ & $x_5$ & $x_5$ & - \\
    2 & $x_4$ & $x_4$ & $x_4$ & -\\
    3\label{seehere} & $x_3$ & $x_3$ & $x_3$ & -\\
    4 & $x_2$ & $x_2$ & $x_3 \oplus x_5 \oplus 1$ & -\\
    5 & $x_1$ & $x_1$ & $x_3 \oplus x_4 $ & -\\
    6 & $x_5^2$ & - & - & $x_5^2-x_5$\\
   
    7 & $x_4x_5$ & $x_4x_5$ & $\frac{1}{2}[\reduce{x_4}{G_1}+\reduce{x_5}{G_1}$ & -\\
     &  &  & $-(x_4 \oplus x_5)]$ & \\
    8 & $x_4^2$ & - & - & $x_4^2-x_4$\\
    9 & $x_3x_5$ & - & - & $x_3x_5-\frac{1}{2}[x_2+x_3+x_5-1]$\\
    10 & $x_3x_4$ & - & - & $x_3x_4 - \frac{1}{2}[-x_1+x_3+x_4]$\\
    11 & $x_3^2$ & - & - & $x_3^2-x_3$\\
    12 & $x_2x_5$ & -  & - & $x_2x_5 - \frac{1}{2}[x_2 + x_3 + x_5 - 1]$\\
    13 & $x_2x_4$ & $x_2x_4$ & $\frac{1}{2}[{x_2}|_{G_1} + {x_4}|_{G_1}$ & -\\
     &  &  & $ - (x_3\oplus x_4 \oplus x_5 \oplus 1) ]$ & \\
    14 & $x_2x_3$ & - & - & $x_2x_3-\frac{1}{2}[x_2+x_3+x_5-1]$\\
    15 & $x_2^2$ & - & - & $x_2^2-x_2$\\
    16 & $x_1x_5$ & - & - & $x_1x_5+x_2x_4-\frac{1}{2}[x_1+x_2+x_4+x_5-1]$\\
    17 & $x_1x_4$ & - & - & $x_1x_4-\frac{1}{2}[x_1-x_3+x_4]$\\
    18 & $x_1x_3$ & - & - & $x_1x_3-\frac{1}{2}[x_1+x_3-x_4]$\\
    19 & $x_1x_2$ & - & - & -\\
    20 & $x_1^2$ & - & - & $x_1^2-x_1$\\
    
    
\end{tabular}
    \caption{Example}
    \label{tab:example}
\end{table}

\section{Conclusion}
The $\textsc{IMP}_d$ tractability for combinatorial ideals has useful practical applications as it implies bounded coefficients in Sum-of-Squares proofs.
A dichotomy result between ``hard'' (NP-hard) and ``easy'' (polynomial time) $\textsc{IMP}$s was recently achieved for the $\textsc{IMP}_0$ ~\cite{Bulatov17,Zhuk17} over the finite domain nearly thirty years after that over the Boolean domain \cite{Schaefer78}. The $\textsc{IMP}_d$ for $d=O(1)$ over the Boolean domain was tackled by Mastrolilli \cite{MonaldoMastrolilli2019} based on the classification of the $\textsc{IMP}$ through polymorphisms, where the complexity of the $\textsc{IMP}_d$ for five of six polymorphisms was solved. We solve the remaining problem, i.e. the complexity of the $\textsc{IMP}_d(\Gamma)$ when $\Gamma$ is closed under the ternary minority polymorphism. This is achieved by showing that the $d$-truncated reduced \text{Gr\"{o}bner}  basis can be computed in polynomial time, thus completing the missing link in the dichotomy result of \cite{MonaldoMastrolilli2019}. 

Moreover, we believe the techniques described in this paper can be generalized for a finite domain with prime $p$ elements, as constraints that are linear equations (mod $p$) are associated with an affine polymorphism \cite{Jeavons_UnifyingFramework1995}. We claim that the $\textsc{IMP}_d$ is tractable for problems that are constrained as linear equations (mod $p$). This is a step in identifying the borderline of tractability, if it exists, for the general $\textsc{IMP}_d$.
We believe that generalizing the dichotomy results of solvability of the IMP$_d$ for a finite domain is an interesting and challenging goal that we leave as an open problem.






{\small
\bibliographystyle{abbrv}
