Régis Barbanchon (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.