Introduction à la complexité.
Ces notes de cours sont principalement dédiées aux problèmes de décision dans les classes P et NP. Ces notes de cours sont le résultat d'un travail de collaboration avec Olivier Bournez (qui lui continue à faire le cours et pas moi).
Cours
Enoncé des exercices :
- Voici un ensemble de problèmes sur la NP-Complétude avec correction .pdf. Voici le contenu.
- Rappel succinct de cours
- exercices sur la notion de décision
- exercices sur la notion de réduction polynomiale.
- exercices sur les preuves NP-complétudes sur les problèmes de logique
- différentes variantes du problème cycle hamiltonien
- exercices sur les preuves NP-complétudes sur les problèmes de graphes
- exercices sur les preuves NP-complétudes sur les problèmes utilisant des entiers