skip to content

The computational complexity of quantified constraint satisfaction

Monday 20th February 2006 - 11:00 to 12:00
INI Seminar Room 1

The constraint satisfaction problem (CSP) is a well-acknowledged framework for modelling and solving computational search problems. A more expressive framework that generalizes the CSP is the quantified constraint satisfaction problem (QCSP). Problems from areas as diverse as graph coloring, game playing, database theory, and non-monotonic reasoning can be naturally formulated in these frameworks.

Both of these problems are, in their general formulation, computationally intractable; the CSP is NP-complete, whereas the QCSP is PSPACE-complete. This intractability has motivated the pursuit of restricted cases of these problems that are tractable. One way to restrict these problems is by prespecifying the types of constraints that may appear. This line of work has its origins in a 1978 paper of Schaefer, who achieved a complexity classification of constraints over a two-element domain, but left open the question of such a classification over domains of larger size. Over the past decade, there has been dramatic progress on this question, largely due to a link between universal algebra and CSP complexity that has been identified.

This talk demonstrates how, with this link, algebraic techniques can be used to study QCSP complexity. We develop a new methodology for proving QCSP tractability results called collapsibility, which allows us to

- unify and identify common structure among the initial QCSP tractability results, which were proved using disparate proof techniques (in different decades!), and

- derive new QCSP tractability results.

Time permitting, we will also discuss recent progress on the case of 3-element QCSP.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons