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.
