Résumé :
|
Cet ouvrage présente certains résultats importants de la théorie de la complexité : son objet est la classification des problèmes suivant l'importance des ressources nécessaires à leur résolution. L'origine de cette théorie apparaît dans l'étude des problèmes difficiles à résoudre sur un ordinateur. Ce domaine, considérablement développé au cours des vingt dernières années, concentre actuellement une large part de la recherche en informatique. Sommaire : 1. Complexité : le temps et l'espace - 2. Définissabilité - 3. Définitions inductives et logique du second ordre - 4. La complexité en temps : les classes P et NP - 5. Modèles de calcul parallèle - 6. La complexité en espace : L, FL, NL, PESPACE - 7. Classes probabilistes - 8. Approximation - 9. Classes au-dessus de NP - 10. Logique et calculabilité Bibliographie - Index
|