Travaux dirigés
TD n°1 [pdf]
Le problème de correspondance de Post, et d'autres exercices sur la récursivité.
TD n°2 [pdf]
Un exemple de problème NP-complet : le jeu Cubic.
TD n°3 [pdf]
Un exemple de problème PSPACE-complet : géographie, noyé dans un énoncé qui parle de tout à la fois.
TD n°4 [pdf]
Les bases de la complexité de Kolmogorov : définition, premières propriétés et quelques applications.
Partiel
Partiel de l'année 2005 - 2006 [pdf][corrigé]
Quelques questions de cours pour montrer qu'une variante simple de SAT est NP-complète. Puis un problème où l'on prouve qu'il est NP-complet de déterminer s'il est possible de gagner en un coup à partir d'une configuration du jeu phutball inventé par John Conway par réduction au problème 3-SAT.