Classes de complexité

Introduction

Les classes de complexité regroupent les problèmes de décision selon les ressources nécessaires (temps, espace, déterminisme).

Classe	Type d’algorithme	Ressource bornée	Description
Classe P	Déterministe	Temps polynomial	Problèmes « faciles »
Classe NP	Non-déterministe	Temps polynomial	Vérification rapide d’une solution
Classe co-NP	Non-déterministe	Temps polynomial	Complémentaire de NP
Classe PSPACE	Déterministe	Espace polynomial	Peut prendre du temps exponentiel, mais mémoire bornée
Classe NSPACE	Non-déterministe	Espace polynomial	Même puissance que PSPACE (Savitch)

Relations entre classes

• $P\subseteq NP$
• $P=co\text{-}P$
• $NP\subseteq PSPACE$
• $PSPACE=NSPACE$
• $NP\ne co\text{-}NP$ (conjecturé)
• $P=NP$ ? (problème ouvert)

Théorèmes

Théorème de Cook-Levin (1971)

→ SAT est le premier problème NP-complet.
Il montre que tout problème de NP se réduit polynômialement à SAT.

Théorème de Savitch (1970)

$NSPACE=PSPACE$
Le non-déterminisme n’apporte aucun avantage en espace.

Relation entre co-NP et NP

→ Si $NP=co\text{-}NP$, alors $P=NP$ (et réciproquement).
Preuve donnée en Classe co-NP.

Diagramme des inclusions

TODO