915 - Classes de complexité. Exemples.2021

Rapport du jury 2019

Le jury attend que le candidat aborde à la fois la complexité en temps et en espace. Il faut naturellement exhiber des exemples de problèmes appartenant aux classes de complexité introduites, et montrer les relations d’inclusion existantes entre ces classes, en abordant le caractère strict ou non de ces inclusions. Le jury s’attend à ce que les notions de réduction polynomiale, de problème complet pour une classe, de robustesse d’une classe vis à vis des modèles de calcul soient abordées. $\\$ Se focaliser sur la décidabilité dans cette leçon serait hors sujet.