论文标题
理想的会员问题和阿贝尔团体
The Ideal Membership Problem and Abelian Groups
论文作者
论文摘要
给定多项式$ f_0，\ dots，f_k $简称$ f_0 $是否属于$ f_1，\ dots，f_k $生成的理想。在此问题的搜索版本中，任务是找到这一事实的证明。 IMP是许多应用程序的众所周知的基本问题，例如，它基于许多基于多项式的证明系统，例如Nullstellensatz，多项式演算和方形总和。尽管IMP通常是棘手的，但在许多重要情况下，它可以有效地解决。 Mastrolilli [Soda'19]对由约束满意度问题（CSP）引起的IMPS进行了系统研究，由约束语言（表示IMP（$γ$））进行了参数。这一研究线的最终目标是将所有这些不适用于其复杂性。 Mastrolilli实现了这一目标，该目标是由CSP（$γ$）引起的，其中$γ$是一种布尔的约束语言，而Bulatov和Rafiey [Arxiv'21]将这些结果提出了几个CSP的CSP案例。在本文中，我们考虑了CSP在“仿射”约束语言上产生的IMB，其中约束是阿贝尔群体直接产品的亚组（或其cosets）。这种CSP包括线性方程式系统，被认为是最重要的可拖动CSP的类型之一。 Bharathi和Mastrolilli [MFCS'21]之前已经考虑了一些问题的特殊情况，用于线性方程模拟2，而Bulatov和Rafiey [Arxiv'21]已涉及$ GF（P）$，$ P $ PRIME的线性方程系统。在这里，我们证明，如果$γ$是一种仿射约束语言，那么假设输入多项式具有界限，则可以在多项式时间内解决IMP（$γ$）。
Given polynomials $f_0,\dots, f_k$ the Ideal Membership Problem, IMP for short, asks if $f_0$ belongs to the ideal generated by $f_1,\dots, 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.
