Évènements

September 2018
21 September 2018

Séminaire CaNa : nombre de points fixes des réseaux Booléen : complexité algorithmique, Florian Bridoux

Résumé: Dans cette présentation nous allons nous intéresser aux réseaux booléens (RB).  Un RB de taille n peut être vu comme une fonction f: {0,1}^n -> {0,1}^n ou bien comme un produit de n fonctions f_1, f_2, ..., f_n de {0,1}^n à {0,1}. Un problème classique est le calcul du nombre de points fixes, c’est-à-dire le nombre de configurations x dans {0,1}^n tel que f(x) = x. Un objet souvent utilisé (et qui justifie la terminologie de « réseaux ») quand on s’intéresse aux réseaux booléens est le graphe d’interaction.  Il s'agit d'un graphe à n sommets numérotés de 1 à n tel qu'il y a un arc entre le sommet i et j ssi la valeur de f_j(x) dépendant de la i-eme composante de x pour un certain x (= le sommet i "a une influence" sur j). Chaque RB a son graphe d’interaction mais un même graphe d’interaction peut correspondre à de nombreux RBs.  Nous allons noter F(G) l'ensemble des RBs correspondant à un certain graphe d’interaction G. Et nous allons nous intéresser à la question: "Étant donné G et un entierk, existe-t-il f dans F(G) qui a au moins/au plus k points fixes?" Nous allons voir que selon la nature de k et l’exacte question posée, le problème peut appartenir à différentes classe de complexité allant de P à NEXPTIME.

Tutelles