On the complexity of CSP-based ideal membership problems
Andreĭ A. Bulatov, Akbar Rafiey · 2022
In this paper we consider the Ideal Membership Problem (IMP for short), in which we are given polynomials f0,f1,…,fk and the question is to decide whether f0 belongs to the ideal generated by f1,…,fk. 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 (SOS). In such applications the IMP usually 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 solution algorithm.