Paper Info
Title
PROMISE CONSTRAINT SATISFACTION: ALGEBRAIC STRUCTURE AND A SYMMETRIC BOOLEAN DICHOTOMY
Abstract
A classic result due to Schaefer [Proceedings of STOC 78, ACM, 1978, pp. 216-226] 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 Gamma consists of a pair (Psi(P), Psi(Q)) of CSPs with the same set of variables such that for every (P, Q) is an element of Gamma, P(x(i1) , ..., x(ik)) is a clause of Psi(P), if and only if Q(x(i1 ), ..., x(ik)) is a clause of Psi(Q). The promise problem PCSP(Gamma) is to distinguish, given (Psi(P), Psi(Q)), between the cases Psi(P) is satisfiable and Psi(Q) is unsatisfiable. Many problems such as approximate graph and hypergraph coloring as well as the (2 + epsilon)-SAT problem due to Austrin, Guruswami, and Hastad [SIAM T. Comput., 46 (2017), pp. 1554-1573] can be placed in this framework. This paper is motivated by the pursuit of understanding the computational complexity of Boolean PCSPs, determining for which F the associated PCSP is polynomial-time tractable or NP-hard. As our main result, we show that PCSP(Gamma) exhibits a dichotomy (it is either polynomial-time tractable or NP-hard) when the relations in Gamma are symmetric and allow for negations of variables. In particular, we show that every such polynomial-time tractable Gamma can be solved via either Gaussian elimination over F-2 or a linear programming relaxation. We achieve our dichotomy theorem by extending the (weak) polymorphism framework of Austrin, Guruswami, and HAstad which itself is a generalization of the algebraic approach used by polymorphisms 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.
Year
DOI
Venue
2021
10.1137/19M128212X
SIAM JOURNAL ON COMPUTING
Keywords
DocType
Volume
constraint satisfaction, promise problem, polymorphism, linear programming, PCP theorem
Journal
50
Issue
ISSN
Citations 
6
0097-5397
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Joshua Brakensiek126.80
V. Guruswami23205247.96