Exercices corrigés — Décidabilité et classes de complexité (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Le test de primalité naïf est-il polynomial ?
- Du seuil à l'optimum
- Le certificat vide
- Un certificat pour la réponse « non » ?
- Lire une réduction dans le bon sens
- Deux problèmes, une réduction d'une ligne
- Le sac à dos, et le mot « pseudo »
- Écrire un vérificateur
- L'arrêt sur l'entrée vide
- « Il suffit de l'exécuter »
- Probleme – SAT : vérifier est facile, chercher ne l'est pas
- Probleme – -SAT est linéaire
- Probleme – Une réduction depuis SAT
- Probleme – Le problème de l'arrêt : ce qu'il interdit vraiment
- Probleme – Du seuil à l'approximation garantie : la couverture par sommets