论文标题
关于基于CSP的理想会员问题的复杂性
On the Complexity of CSP-based Ideal Membership Problems
论文作者
论文摘要
在本文中，我们考虑了理想的会员资格问题（简称IMP），其中我们将获得真实的多项式$ f_0，f_1，f_1，\ dots，f_k $，问题是决定$ f_0 $是否属于$ f_1，\ dots，dots，f_k $产生的理想。在更严格的版本中，任务也是要找到这一事实的证明。 IMP基于许多基于多项式的证明系统，例如零史塔兹，多项式演算和方形总和。在大多数此类应用中，IMP涉及所谓的组合理想，这些理想是由各种离散组合问题引起的。这种限制使IMP变得更加容易，在某些情况下，可以使用有效的算法来解决它。 本文的第一部分遵循了Mastrolilli [Soda'19]的工作，他对$ CSP（γ）$的约束满意度问题（CSP）的系统进行了系统研究，即CSP，其中约束类型仅限于Set $γ$的关系。我们表明，许多CSP技术可以转化为IMPS，从而使我们能够显着改善研究IMP的复杂性的方法。我们还为IMP开发了通用代数技术，该技术在CSP的研究中非常有用。这使我们能够证明IMP的障碍和三个足够的条件是一般必要条件。足够的条件包括由$ gf（p）$，$ p $ prime的线性方程系统产生的小动物，以及通过特殊类型的多态性定义的某些条件。 我们的工作在相当的位数（SOS）证明及其可容器以及组合问题的theta体的研究（构造）方面有几种后果和应用。
In this paper we consider the Ideal Membership Problem (IMP for short), in which we are given real polynomials $f_0,f_1,\dots, f_k$ and the question is to decide whether $f_0$ belongs to the ideal generated by $f_1,\dots,f_k$. In the more stringent version the task is also to find a proof of this fact. The IMP underlies many proof systems based on polynomials such as Nullstellensatz, Polynomial Calculus, and Sum-of-Squares. In the majority of such applications the IMP involves so called combinatorial ideals that arise from a variety of discrete combinatorial problems. This restriction makes the IMP significantly easier and in some cases allows for an efficient algorithm to solve it. The first part of this paper follows the work of Mastrolilli [SODA'19] who initiated a systematic study of IMPs arising from Constraint Satisfaction Problems (CSP) of the form $CSP(Γ)$, that is, CSPs in which the type of constraints is limited to relations from a set $Γ$. We show that many CSP techniques can be translated to IMPs thus allowing us to significantly improve the methods of studying the complexity of the IMP. We also develop universal algebraic techniques for the IMP that have been so useful in the study of the CSP. This allows us to prove a general necessary condition for the tractability of the IMP, and three sufficient ones. The sufficient conditions include IMPs arising from systems of linear equations over $GF(p)$, $p$ prime, and also some conditions defined through special kinds of polymorphisms. Our work has several consequences and applications in terms of bit complexity of sum-of-squares (SOS) proofs and their automatizability, and studying (construction of) theta bodies of combinatorial problems.
