Collapsibility and Consistency in Quantified Constraint Satisfaction

The concept of consistency has pervaded studies of the con-straint satisfaction problem. We introduce two concepts, which are inspired by consistency, for the more general framework of the quantified constraint satisfaction problem (QCSP). We use these concepts to derive, in a uniform fash-ion, proofs of polynomial-time tractability and correspond-ing algorithms for certain cases of the QCSP where the types of allowed relations are restricted. We not only unify exist-ing tractability results and algorithms, but also identify new classes of tractable QCSPs