Friday, November 30, 2007
3:30 pm, MC 5158

Mike Molloy
University of Toronto

The Resolution Complexity of Random Constraint Satisfaction Problems

Constraint satisfaction problems (CSP's) are generalizations of CNF boolean formulas. We are given a set of variables, and a domain of values that the variables can take. Some subsets of the variables have ``constraints'' which restrict the value-assignments that can be made to those variables. A problem is satisfiable if there is an assignment of values to the variables which does not violate any of the constraints. Some well-studied special cases are k-SAT, graph colourability and graph homomorphism.
Random instances of various CSP's appear to be very difficult to solve in practice. Chvátal and Szemerédi proved a theorem explaining this for the case of random 3-SAT: with high probability, the resolution complexity of a random 3-SAT formula with a linear number of clauses will be exponentially high. This implies an exponential lower bound on the running time of any resolution-based algorithm (such as Davis-Putnam and its many variants).

In this talk, we discuss a wide class of models of random constraint satisfaction problems. The main result is that we determine which models from this class will, with high probability, have exponentially high resolution complexity for any linear number of constraints.

This is joint work with Siu On Chan.