Abstract

The constraint satisfaction problem (CSP) is a framework for modelling search problems. An instance of the CSP consists of a set of variables and a set of constraints on the variables; the question is to decide whether or not there is an assignment to the variables satisfying all of the constraints. The quantified constraint satisfaction problem (QCSP) is a generalization of the CSP in which variables may be both universally and existentially quantified. The general intractability of the CSP and QCSP motivates the search for restricted cases of these problems that are polynomial-time tractable.

In this dissertation, we investigate the computational complexity of cases of the QCSP where the types of constraints that may appear are restricted. One of our primary tools is the algebraic approach to studying CSP complexity, which can also be used to study QCSP complexity. We first present a pair of new QCSP tractability results; one of these tractability results is arrived at by developing a sound and complete proof system for QCSPs having a certain form. We then introduce a new concept for proving QCSP tractability results called collapsibility. The key idea behind collapsibility is that for certain cases of the QCSP, deciding an instance can be reduced to deciding an ensemble of instances, all of which have a bounded number of universally quantified variables and are derived from the original instance by ``collapsing'' together universally quantified variables. Collapsibility provides a uniform proof technique for deriving QCSP tractability results which we use both to give alternative proofs of the initial pair of tractability results, as well as to give further tractability results.

Table of Contents

1. Introduction
2. Preliminaries
3. A Pair of Tractability Results
4. Collapsibility
5. Complexity of 2-Semilattice Polymorphisms
6. Conclusions