Jean-Francis Michon (LIFAR)

La mesure traditionnelle de complexité des fonctions booléennes à n variables (depuis SHANNON) est celle des circuits booléens. Elle est, en général, très difficile à calculer. On montre comment d’autres mesures, plus calculables, pourraient etre définies et quelles difficultés on doit surmonter pour en faire de “vraies” mesures. Elles proviennent de la théorie des Diagrammes de Décision Binaire de R. Bryant et s’interprètent aussi en terme de minimisation d’automates. Je présente l’état actuel de mes connaissances sur ces mesures.

Mon exposé ne demande aucune connaissance préalable en dehors des graphes, automates , machine de Turing. Toutes les notions de complexité utilisées seront rappelées. Rien que des choses élémentaires en somme !

Références

  • Clote et Kranakis, Boolean functions and computation models (Springer 2002)
  • JF MICHON Maximal complexity of canonical graphs of boolean functions (soumis à Eurocrypt 2003)