Florent Madelaine (LIMOS, Université de Clermont-Ferrand)

The Quantified Constraint Satisfaction Problem (QCSP) allows to model uncertainty or lack of control of some variables. This extension of the classical setting of Constraint Satisfaction comes at a price : the problem is Pspace-complete rather than NP-complete. An ongoing program aims at classifying the complexity of the QCSP for each constraint language, and known results suggest that the QCSP could follow a trichotomy between Pspace- complete, NP-complete and tractability (in Ptime). However, most complexity results for the QCSP are of the form NP-hard vs tractable. While these results are important and interesting, we wish to better understand the Pspace- complete vs NP question in QCSPs.

Collapsibility is a natural property of a constraint language introduced by Hubie Chen, which implies a drop in complexity of the associated QCSP from Pspace-complete to NP. This property covers all known natural example of constraint languages with a QCSP in NP.

In this talk, we will present some recent results on collapsibility. Our main result is that we can decide in several natural cases whether a constraint language is collapsible.

This is joint work with Barnaby Martin of the Middlesex.