论文标题
布尔少数民族的理想会员问题
Ideal Membership Problem for Boolean Minority
论文作者
论文摘要
理想的会员问题（IMP）测试如果输入多项式$ f \ in \ mathbb {f} [x_1，\ dots，x_n] $，带有来自字段$ \ mathbb {f} $的系数，属于给定的理想$ i \ subseteq \ subSeteq \ subseteq \ subseteq \ mathbb {f} $这是许多重要应用的众所周知的基本问题，尽管在一般情况下众所周知。在本文中，我们考虑了编码组合问题的多项式理想的IMP，并且输入多项式$ f $最多具有$ d = o（1）$的imp（我们称此问题IMP $ _D $）。 A dichotomy result between ``hard'' (NP-hard) and ``easy'' (polynomial time) IMPs was recently achieved for Constraint Satisfaction Problems over finite domains [Bulatov FOCS'17, Zhuk FOCS'17] (this is equivalent to IMP$_0$) and IMP$_d$ for the Boolean domain [Mastrolilli SODA'19], both based on the classification通过称为多态性的功能。五种多态性的IMP $ _D $的复杂性在[Mastrolili Soda'19]中得到了解决，而对于三元少数族裔多态性，它被错误地宣布已被先前的结果解决。事实上，对于三元少数族裔多态性，IMP $ _D $的复杂性是开放的。在本文中，我们通过证明了布尔组合理想的IMP $ _D $来提供丢失的链接，其约束在少数族裔多态性下封闭的约束可以在多项式时间内解决。该结果以及[Mastrolili Soda'19]中的结果完成了IMP $ _D $的确切范围的确定性，以识别布尔域上受约束的问题。本文的动机是通过理解O'Donnell [ITCS'17]提出的平方符号证明的一点复杂性的问题。 Raghavendra和Weitz [iCalp'17]展示了组合理想的IMP $ _D $ tractability如何意味着在平方符号证明中的有限系数。
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) IMPs was recently achieved for Constraint Satisfaction Problems over finite domains [Bulatov FOCS'17, Zhuk FOCS'17] (this is equivalent to IMP$_0$) and IMP$_d$ for the Boolean domain [Mastrolilli SODA'19], both based on the classification of the IMP through functions called polymorphisms. The complexity of the IMP$_d$ for five polymorphisms has been solved in [Mastrolilli SODA'19] whereas for the ternary minority polymorphism it was incorrectly declared to have been resolved by a previous result. As a matter of fact the complexity of the 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 result, along with the results in [Mastrolilli SODA'19], completes the identification of the precise borderline of tractability for the IMP$_d$ for constrained problems over the Boolean domain. This paper is motivated by the pursuit of understanding the issue of bit complexity of Sum-of-Squares proofs raised by O'Donnell [ITCS'17]. Raghavendra and Weitz [ICALP'17] show how the IMP$_d$ tractability for combinatorial ideals implies bounded coefficients in Sum-of-Squares proofs.
