On the complexity of CSP-based ideal membership problems

DOI10.1145/3519935.3520063MaRDI QIDQ6083496zbMATH OpenOpenAlexWikidataFDO

Authors Andrei A. Bulatov, Akbar Rafiey

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.03700

zbMATH Keywords

constraint satisfaction problemsGroebner basispolymorphismspolynomial ideal membership

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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(Gamma)$, that is, CSPs in which the type of constraints is limited to relations from a set $Gamma$. 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.

Recommendations

• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• On the complexity of \#CSP
• On the parallel complexity of the polynomial ideal membership problem
• Mathematical Foundations of Computer Science 2004
• The complexity of membership problems for circuits over sets of integers
• Approximation Algorithms for CSPs
• On the CSP Dichotomy Conjecture

Cited in

(9)

• scientific article; zbMATH DE number 939812 (Why is no real title available?)
• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• scientific article; zbMATH DE number 7724189 (Why is no real title available?)
• Short proofs of ideal membership
• Bi-arc digraphs: recognition algorithm and applications
• Computational complexity of sum-of-squares bounds for copositive programs
• Ideal membership problem for Boolean minority and dual discriminator
• The ideal membership problem and abelian groups
• On the degree automatability of sum-of-squares proofs

This page was built for publication: On the complexity of CSP-based ideal membership problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083496)