Etienne Grandjean (GREYC)

La question centrale de cet exposé est la suivante: quels rapports peut-on établir entre la complexité algorithmique d’un problème (son temps de calcul, etc.) et la façon de définir ce problème dans une certaine logique ?

Mon exposé déclinera cette question en 2 autres questions:

  1. La question de l’efficacité: comment la logique peut-elle aider à construire des algorithmes “génériques” pour résoudre “efficacement” telle classe de problèmes ?
  2. La question de la compréhension: peut-on caractériser exactement telle classe de complexité en logique ? autrement dit, dans quel cas a-t-on une égalité de la forme

“classe de complexité” = “classe de problèmes définie dans telle logique?”

Mon exposé se veut élémentaire. Je pars d’exemples simples et des logiques classiques.

Sur les questions 1 et 2, je présenterai un petit état de l’art avec mon point de vue personnel et beaucoup de questions.