September 24, 2018
Florian Bridoux (LIS - Marseille)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
entier k, 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.