ECCC-Report TR16-183https://eccc.weizmann.ac.il/report/2016/183Comments and Revisions published for TR16-183en-usThu, 06 May 2021 04:52:11 +0300
Revision 2
| Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy |
Joshua Brakensiek,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2016/183#revision2A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{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) \in \Gamma$, $P(x_{i_1}, \cdots, x_{i_k})$ is a clause of $\Psi_P$ if and only if $Q(x_{i_1}, \cdots, x_{i_k})$ 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 studied in the literature such as approximate graph and hypergraph coloring as well as the $(2+\epsilon)$-SAT problem due to Austrin, Guruswami, and Håstad [FOCS '14] can be placed in this framework.
This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs, determining for which $\Gamma$ 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 $\mathbb F_2$ or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH 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.
Thu, 06 May 2021 04:52:11 +0300https://eccc.weizmann.ac.il/report/2016/183#revision2
Revision 1
| Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy |
Joshua Brakensiek,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2016/183#revision1A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{P}$ or $\mathsf{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) \in \Gamma$, $P(x_{i_1}, \hdots, x_{i_k})$ is a clause of $\Psi_P$ if and only if $Q(x_{i_1}, \hdots, x_{i_k})$ is a clause of $\Psi_Q$. The promise problem $\operatorname{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, the $(2+\epsilon)$-SAT problem due to Austrin, Guruswami, and H\aa stad [FOCS '14], and the digraph homomorphism problem can be placed in this framework.
This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs, determining for which $\Gamma$ the associated PCSP is polynomial-time tractable or $\mathsf{NP}$-hard. As our main result, we show that $\operatorname{PCSP}(\Gamma)$ exhibits a dichotomy (it is either polynomial-time tractable or $\mathsf{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 $\mathbb F_2$ or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH 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.
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.Fri, 07 Apr 2017 00:05:07 +0300https://eccc.weizmann.ac.il/report/2016/183#revision1
Paper TR16-183
| Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy |
Joshua Brakensiek,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2016/183A classic result due to Schaefer (1978) classifies all constraint satisfaction problems (CSPs) over the Boolean domain as being either in $\mathsf{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) \in \Gamma$, $P(x_{i_1}, \cdots, x_{i_k})$ is a clause of $\Psi_P$ if and only if $Q(x_{i_1}, \cdots, x_{i_k})$ 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 studied in the literature such as approximate graph and hypergraph coloring as well as the $(2+\epsilon)$-SAT problem due to Austrin, Guruswami, and Håstad [FOCS '14] can be placed in this framework.
This paper is motivated by the pursuit of understanding the computational complexity of Boolean promise CSPs, determining for which $\Gamma$ 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 $\mathbb F_2$ or a linear programming relaxation. We achieve our dichotomy theorem by extending the weak polymorphism framework of AGH 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.
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.Wed, 16 Nov 2016 17:06:48 +0200https://eccc.weizmann.ac.il/report/2016/183