Leçon 915 : Classes de complexité. Exemples.

(2016) 915
(2018) 915

Dernier rapport du Jury :

(2017 : 915 - Classes de complexité. Exemples.) 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. Parler de décidabilité dans cette leçon serait hors sujet.

(2015 : 915 - Classes de complexité : exemples.) 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. Le jury s'attend à ce que le caractère strict ou non de ces inclusions soit abordé, en particulier le candidat doit être capable de montrer la non-appartenance de certains problèmes à certaines classes. Parler de décidabilité dans cette leçon serait hors sujet.

Développements :

Plans/remarques :

2016 : Leçon 915 - Classes de complexité : exemples.


2015 : Leçon 915 - Classes de complexité : exemples.


Retours d'oraux :

Pas de retours pour cette leçon.

Références utilisées dans les versions de cette leçon :

Introduction to the theory of computation , Sipser (utilisée dans 12 versions au total)
Computational Complexity: A Modern Approach, Sanjeev Arora, Boaz Barak (utilisée dans 4 versions au total)
Computational complexity , Papadimitriou (utilisée dans 7 versions au total)