Vérifier l'algèbre linéaire en temps linéaire

Nous commencerons par une brève introduction à la théorie des jeux combinatoires en insistant sur  la notion de complexité définie pour ces jeux.  Quels sont les points communs et les divergences entre cette notion et celle, bien connue, de complexité pour les problèmes de décisions ? Nous présenterons ensuite plusieurs jeux sur les graphes, notamment le jeu  « Geography » et  des variantes du jeu de Nim. Nous montrerons que dans la plus part des cas le problème associé à la détermination de stratégies gagnantes est PSPACE-Dur. Puis en nous restreignant aux graphes bipartis, nous serons capables, en utilisant les couplages, de déterminer efficacement si une position est gagnante ou perdante.