Ce vendredi à 10h30 en salle 301 nous accueillons Florent Madelaine (Université de Caen/Université de Clermont-Ferrand).
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, I will present some new results on collapsibility. Our main result is that we can decide in several natural cases whether a constraint language is collapsible. This relies heavily on the fact that we can relate collapsibility for QCSP with collapsibility for the Pi2-restrictions of QCSP (when the values of universal variables are all known before existential variables). If times allows I will also explain how this result motivates further a purely algebraic gap question on size of generating sets for the sequence of powers of an algebra (polynomial vs exponential).