Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP La classe PEspace Reductions parcimonieuses

Les algorithmes La theorie de la complexite: un peu d'histoire La classe P La classe NP La classe PEspace Reductions parcimonieuses Complexite avancee - UMIN 345 Theorie de la NP-Completude (2) Christophe PAUL September 24, 2007 Christophe PAUL Complexite avancee - UMIN 345 Theorie de la NP-Completude (2)

• complexite avancee - umin


• classe co ?


• x1 x2x2


• reductions parcimonieusesquelques


• classe np


• theorie de la complexite