Informatique MPI
Tout le chapitre de calculabilité est au programme. On pourra donner des exercices autour de l'appartenance à la classe P, l'appartenance à la classe NP, les réduction polynomiales, et la NP-dureté et NP-complétude de problèmes de décision.
Le théorème de Cook-Levin (SAT est NP-complet) est à connaître, et on rappelle qu'il est admis ; de même que pour les exercices de décidabilité, il est attendu de savoir que le problème de l'arrêt est indécidable. Il n'est pas attendu de connaître une liste de problèmes indécidables ou NP-complets à l'avance, mais il est bon de savoir que de nombreuses variantes de SAT (CNF-SAT, et les $k$-SAT pour $k \geq 3$) sont NP-complètes (attention, $2$-SAT est dans P).
