The complexity of QCSP : when is it in NP?

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.