The Complexity of the Ideal Membership Problem and Theta Bodies for Constrained Problems Over the Boolean Domain
share
Given an ideal I and a polynomial f the Ideal Membership Problem is to test if f∈ I. This problem is a fundamental algorithmic problem with important applications and notoriously intractable. We study the complexity of the Ideal Membership Problem for combinatorial ideals that arise from constrained problems over the Boolean domain. As our main result, we identify the precise borderline of tractability. By using Gröbner bases techniques, we generalize Schaefer's dichotomy theorem [STOC, 1978] which classifies all Constraint Satisfaction Problems over the Boolean domain to be either in P or NP-hard. Moreover, our result implies necessary and sufficient conditions (assuming P = NP) for the efficient computation of Theta Body SDP relaxations, identifying therefore the precise borderline of tractability for constraint language problems. This paper is motivated by the pursuit of understanding the recently raised issue of bit complexity of Sum-of-Squares proofs [O'Donnell, ITCS, 2017]. Raghavendra and Weitz [ICALP, 2017] show how the Ideal Membership Problem tractability for combinatorial ideals implies bounded coefficients in Sum-of-Squares proofs.
READ FULL TEXT