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.
21 September 2018, 14h0015h00
Salle de réunion du bâtiment modulaire. (Luminy)

Prochains évènements

Retour à l'agenda
20 December 2018

Séminaire CaNa : 20 décembre à 14h : SAT est NP-complet, la preuve !

Résumé : Ne croyez pas ce que l'on vous a dit, le théorème de Cook-Levin n'est pas si difficile que cela à démontrer... J'ai longtemps admis cette preuve, et après l'avoir lue dans le livre de Sylvain Perifel, j'ai envie de la partager ! Venez ajouter LA brique de base à vos connaissances en complexité, ou simplement réviser :-)

Tutelles