Colle 4 : Graphes et classes de complexité

• Décidabilité : Tout le cours.

• Classes de complexité : Tout le cours.

Merci de poser obligatoirement au moins une question de décidabilité ou classe de complexité : montrer qu'un problème est indécidable (réduction depuis ARRET) ou NP-complet (NP + réduction polynomiale depuis SAT).

• Algorithmes d'approximation et Branch and Bound : Tout le cours.

• Algorithmes probabilistes : Tout le cours.