Complexité
Plan détaillé
(cf. [Sip97])
- Complexité en temps et en espace
- complexité en temps et en espace d'une machine
- théorème d'accélération
- changements de modèles
- classes de complexité en temps
- Temps polynomial
- exemples de problèmes en temps polynomial déterministe
- accessibilté dans un graphe
- langages algébriques
- exemples de problèmes en temps polynomial non déterministe
- chemin hamiltonien
- satisfiabilité d'une formule
- Réductions polynomiales
- NP-complétude
- définition de NP-difficile et NP-complet
- NP-complétude de SAT et 3-SAT
- Exemples de problèmes NP-complets
- couverture de sommets
- chemin hamiltonien
- problème de la somme
- Complexité en espace
- liens entre la complexité en temps et en espace
- classes de complexité en espace
- théorème de Savitch
- Espace polynomial
- exemples de problèmes en espace polynomial
- L(M) = A* pour un automate non déterministe M
- relations entre les classes P, NP, SPACE et EXPTIME.
- PSPACE-complétude
- définition
- PSPACE-complétude de la vérité des formules booléennes quantifiées
- Alternance
- définition des machines alternantes
- automates alternants
- classes de complexité