Search

We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of the modulus M. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: \sanstwo -\sansS \sansA \sansT, \sansH \sansO \sansR \sansN -\sansS \sansA \sansT, and \sansL \sansI \sansN -\sanstwo (linear equations mod 2). We classify the moduli M for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The \sansH \sansO \sansR \sansN -\sansS \sansA \sansT case is connected to the covering complexity of polynomials representing the \sansN \sansA \sansN \sansD function mod M. The \sansL \sansI \sansN -\sanstwo case is tied to the sparsity of polynomials representing the \sansO \sansR function mod M, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by N\"agele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for \sansH \sansO \sansR \sansN -\sansS \sansA \sansT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite M. [ABSTRACT FROM AUTHOR]

A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in P or NP-hard. This paper considers a promise-problem variant of CSPs called PCSPs. A PCSP over a finite set of pairs of constraints Γ consists of a pair (ΨP,ΨQ) of CSPs with the same set of variables such that for every (P,Q)∈Γ, P(xi1,...,xik) is a clause of ΨP if and only if Q(xi1,...,xik) is a clause of ΨQ. The promise problem PCSP(Γ) is to distinguish, given (ΨP,ΨQ), between the cases ΨP is satisfiable and ΨQ is unsatisfiable. Many natural problems including approximate graph and hypergraph coloring can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs. As our main result, we show that PCSP(Γ) exhibits a dichotomy (it is either polynomial time solvable or NP-hard) when the relations in Γ are symmetric and allow for negations of variables. We achieve our dichotomy theorem by extending the weak polymorphism framework of Austrin, Guruswami, and Håstad [FOCS '14] which itself is a generalization of the algebraic approach to study CSPs. In both the algorithm and hardness portions of our proof, we incorporate new ideas and techniques not utilized in the CSP case. Furthermore, we show that the computational complexity of any promise CSP (over arbitrary finite domains) is captured entirely by its weak polymorphisms, a feature known as Galois correspondence, as well as give necessary and sufficient conditions for the structure of this set of weak polymorphisms. Such insights call us to question the existence of a general dichotomy for Boolean PCSPs case. [ABSTRACT FROM AUTHOR]