La théorie de la complexité est basée sur une classification des différents problèmes. Deux classes sont importantes à connaître : et .
et 
.