Georgia Institute of Technology College of Sciences

For relations {R_1,..., R_k} on a finite set D, the {R_1,...,R_k}-CSP is a computational problem specified as follows: Input: a set of constraints C_1, ..., C_m on variables x_1, ..., x_n, where each constraint C_t is of form R_{i_t}(x_{j_{t,1}}, x_{j_{t,2}}, ...) for some i_t in {1, ..., k} Output: decide whether it is possible to assign values from D to all the variables so that all the constraints are satisfied. The CSP problem is boolean when |D|=2. Schaefer gave a sufficient condition on the relations in a boolean CSP problem guaranteeing its polynomial-time solvability, and proved that all other boolean CSP problems are NP-complete. In the planar variant of the problem, we additionally restrict the inputs only to those whose incidence graph (with vertices C_1, ..., C_m, x_1, ..., x_m and edges joining the constraints with their variables) is planar. It is known that the complexities of the planar and general variants of CSP do not always coincide. For example, let NAE={(0,0,1),(0,1,0),(1,0,0),(1,1,0),(1,0,1),(0,1,1)}). Then {NAE}-CSP is NP-complete, while planar {NAE}-CSP is polynomial-time solvable. We give some partial progress towards showing a characterization of the complexity of planar boolean CSP similar to Schaefer's dichotomy theorem.Joint work with Martin Kupec.