Computational complexity

Papadimitriou

Utilisée dans les 1 développements suivants :

Graphes et formules logiques : 2-SAT est NL-complet, CLIQUE est NP-complet

Utilisée dans les 3 leçons suivantes :

915 (2021) Classes de complexité. Exemples.
913 (2021) Machines de Turing. Applications.
28 (2022) Formules du calcul propositionnel : représentation, formes normales, satisfiabilité. Applications.

Utilisée dans les 2 versions de développements suivants :


Utilisée dans les 5 versions de leçons suivantes :