Jeu et complexité : une variante PSPACE-Dur du jeu de Nim.

Nous commencerons par présenter la notion de complexité pour les jeux combinatoires à deux joueurs. Quels sont les points communs et les divergences entre cette notion et celle, plus connue, de complexité pour les problèmes de décisions? Nous présenterons ensuite plusieurs version du jeu de Nim sur les graphes, et nous montrerons que dans la plus part des cas elles sont PSPACE-Dur. Cependant, en nous restreignant aux graphes bipartis, nous serons capables, en utilisant les couplages, de déterminer efficacement si une position et gagnante ou perdante.

Et toujours, la page du séminaire : http://www-fourier.ujf-grenoble.fr/~magotjm/seminaire_comprehensible/