Journée IM-IA

Journée « Beyond NP »

10 mai 2017

Université Paris-Diderot

 

Journée commune GDR IM – préGDR IA

Organisateurs: Arnaud Durand et Pierre Marquis.

 

Les progrès réalisés en pratique ces dernières années concernant la résolution d’instances de SAT/CSP ouvrent la voie à l’étude et à la conception d’algorithmes de résolution de problèmes qui sont vraisemblablement au delà de NP (dont #SAT, QBF) et que des développements tant théoriques que plus appliqués vont déjà dans cette direction (NP-preprocessing, approche CEGAR, beyondnp.org, etc.).

L’objectif de cette journée est de réunir les chercheurs des communautés d’informatique fondamentale et d’intelligence artificielle qui s’intéressent aux contraintes (en un sens très général) et à l’évaluation de requêtes pour échanger et confronter les approches et les points de vue, en particulier sur ces problématiques au delà de la décision (comptage, énumération, agrégation, …)

Voici le programme détaillé de la journée :

– 9h30-10h : accueil

– 10h-10h30 : Laurent Simon (Bordeaux)

« Efficiency of SAT solvers: why do they work so well? » [slides]

– 10h30-11h30 : Joao Marques Silva (Lisbonne)

« Computing with Oracles: From NP to Beyond NP and Back Again » [slides]

– 11h30-12h10 : George Katsirelos (INRA)

« Optimization with Weighted Constraint Satisfaction » [slides]

– 12h10-14h lunch + discussion

– 14h-15h: Hubie Chen (San Sebastian)

« A Personal Perspective on SAT and CSP: Tractability, Complexity, Quantification, Proofs » [slides]

– 15h-15h30: Florent Madelaine (Clermont)

« Complexity of model checking parameterised by the model » [slides]

– 15h30-16h10: Antoine Amarilli (Telecom Paris Tech)

« A Circuit-Based Approach to Efficient Enumeration » [slides]

– 16h10-17h : discussion

La journée est ouverte à celles et ceux qui sont intéressés par le thème retenu et/ou souhaitent participer aux discussions qui suivront.