Calculabilité, décidabilité et classes de complexité

Notions	Commentaires
Problème de décision. Taille d’une instance. Complexité en ordre de grandeur en fonction de la taille d’une instance. Opération élémentaire. Complexité en temps d’un algorithme. Classe P.	Les opérations élémentaires sont les lectures et écritures en mémoire, les opérations arithmétiques, etc. La notion de machine de Turing est hors programme. On s’en tient à une présentation intuitive du modèle de calcul (code exécuté avec une machine à mémoire infinie). On insiste sur le fait que la classe P concerne des problèmes de décision.
Réduction polynomiale d’un problème de décision à un autre problème de décision.	On se limite à quelques exemples élémentaires.
Certificat. Classe NP comme la classe des problèmes que l’on peut vérifier en temps polynomial. Inclusion P ⊆ NP.	Les modèles de calcul non-déterministes sont hors programme.
NP-complétude. Théorème de Cook-Levin (admis) : SAT est NP-complet.	On présente des exemples de réduction de problèmes NP-complets à partir de SAT. La connaissance d’un catalogue de problèmes NP-complets n’est pas un objectif du programme.
Transformation d’un problème d’optimisation en un problème de décision à l’aide d’un seuil.
Notion de machine universelle. Problème de l’arrêt.

On prend soin de distinguer la notion de complexité d’un algorithme de la notion de classe de complexité d’un problème. Le modèle de calcul est une machine à mémoire infinie qui exécute un programme rédigé en OCaml ou en C. La maîtrise ou la technicité dans des formalismes avancés n’est pas un objectif du programme.

Compléments AGREG : Calculabilité, complexité

• Modèle de calcul. Machines de Turing : définition, principales variantes (ruban biinfini vs infini, machine à plusieurs rubans). La machine de Turing est le modèle de calcul retenu pour l’étude des notions qui suivent.
• Calculabilité : universalité, décidabilité, indécidabilité. Problème de l’arrêt.
• Complexité : complexité en temps et en espace, classe P. Acceptation par certificat, classe NP. Réduction polynomiale. NP-complétude. Théorème de Cook.
  La notion de machine de Turing non déterministe n’est pas exigible aux épreuves 1, 2 et 3.a de l’écrit, ni aux épreuves orales.