Ce domaine a ouvert la voie dans la décennie 1970 à une analyse d'un niveau plus fin, appeléethéorie des classes de complexité, où l'on se pose des questions du type suivant : peut-on décomposer en facteurs premiers un
nombre de
n chiffres en utilisant un
temps de calcul
t majoré par...