Cher(e)s collègues,
Nous organisons le 10 mai prochain une journée sur le thème « Beyond NP ».
La journée se tiendra dans les locaux de l’Université Paris-Diderot, et plus précisément dans la salle 1021 (susceptible de changer mais ce sera fléché), bâtiment Sophie Germain, 8 Place Aurélie Nemours, dans le 13ème arrondissement.
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? »
– 10h30-11h30 : Joao Marques Silva (Lisbonne)
« Computing with Oracles: From NP to Beyond NP and Back Again »
– 11h30-12h10 : George Katsirelos (INRA)
« Optimization with Weighted Constraint Satisfaction »
– 12h10-14h lunch + discussion
– 14h-15h: Hubie Chen (San Sebastian)
« A Personal Perspective on SAT and CSP: Tractability, Complexity, Quantification, Proofs »
– 15h-15h30: Florent Madelaine (Clermont)
« Complexity of model checking parameterised by the model »
– 15h30-16h10: Antoine Amarilli (Telecom Paris Tech)
« A Circuit-Based Approach to Efficient Enumeration »
– 16h10-17h : discussion
Les exposés seront suivis d’un débat sur l’opportunité de créer un groupe de recherche commun au pré-GDR IA (intelligence artificielle) et au GdR IM (informatique mathématique) ayant pour but d’animer la communauté nationale sur ces thèmes.
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. Toutefois, pour des raisons de logistique, nous demandons aux collègues souhaitant participer à la journée de nous le faire savoir (si ce n’est pas déjà fait) par retour de courriel (durand@math.univ-paris-diderot.fr, marquis@cril.univ-artois.fr).
Venez donc nombreux !
Bien cordialement,
Arnaud Durand et Pierre Marquis.