Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 24 Juin 2014

The complexity of QCSP : when is it in NP?

par 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.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30