Finding Good Assignments for Satisfiable Instances of Boolean CSPs

September 18, 2013

A Boolean constraint satisfaction problem (CSP) is defined by a set of Boolean variables and a collection of constraints on the variables. The goal is to distinguish satisfiable instances from unsatisfiable ones, and find an assignment that satisfies all the constraints if the input is satisfiable. As Schaefer's dichotomy theorem shows, the vast majority of CSPs are NP-complete. However, not all hard CSPs are created equal, some harder than others. To better understand the complexity of CSPs, it is natural to study a relaxed version of the problem, where the goal is to distinguish satisfiable instances from those that are "far" from satisfiable. In this talk, we will discuss algorithm and hardness results for 3-CSPs — problems where each constraint depends on at most 3 variables. We will also present some recent result on k-CSPs as k grows.