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 20 Janvier 2004

Logique, hiérarchies dans NP et problèmes NP-complets minimaux

par Régis Barbanchon (GREYC), Etienne Grandjean (GREYC)

Dès 1974, le théorème de Fagin donnait une caractérisation de la classe des problèmes NP en logique Existentielle du Second Ordre (ESO) : NP = ESO.

Partant de cette caractérisation logique, donc indépendante des machines et du temps, on se pose dans cet exposé deux sortes de questions :

  1. Peut-on établir des hiérarchies strictes de complexité (=difficulté) des problèmes NP à partir de la forme syntaxique des formules ESO qui les caractérisent ?
  2. Quelle(s) est (sont) la (les) formule(s) minimale(s) décrivant un (des) problème(s) NP-complet(s) ?

Dans cet exposé on présente des résultats récents concernant ces deux points :

  1. On établit des résultats partiels sur les liens entre le temps non déterministe et l'arité (= nombre des arguments) des relations et fonctions qui interviennent dans une formule logique ; au-delà, on présente une conjecture et ses conséquences.
  2. On exhibe une formule logique minimale (minimale selon plusieurs critères) qui décrit un problème NP-complet et on montre que cette formule minimale est unique, à symétries près.
GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr