Complexity of Constraint Satisfaction Problems: Exact and Approximate
Is there a common explanation for 2SAT being solvable polynomial time, and Max2SAT being approximable to a 0.91 factor? More generally, it is natural to wonder what characterizes the complexity of exact constraint satisfaction problems (CSP) like 2SAT and what determines the approximation ratios for MaxCSPs like Max2SAT.
A Constraint Satisfaction Problem (CSP) such as 3-SAT, Horn-SAT is specified by a set of predicates. In the exact version, the goal is to find out if an instance of the CSP is completely satisfiable or unsatisfiable. In the approximate version, the goal is to find an assignment that satisfies the maximum number of constraints.
The algebraic dichotomy conjecture attempts to characterize CSPs for which the exact version is easy, while the Unique Games Conjecture yields the correct thresholds of approximability for CSPs. Although posed independently, the two conjectures point to the same underlying characterization for the complexity of a CSP. Specifically, they assert that the complexity of CSP is determined by the existence of "non-trivial polymorphisms" - operations that combine assignments to the CSP in to new assignments. In this talk, we will expand on this emerging connection between the complexities of approximate and exact CSPs.
Date
Speakers
Prasad Raghavendra
Affiliation
University of Washington