Per le classi di complessità così definite, è auspicabile dimostrare che allentando i requisiti sui tempi di calcolo (diciamo) si definisce un insieme più ampio di problemi. In particolare, sebbene il DTIME (n) sia contenuto nel DTIME (n2), sarebbe interessante sapere se l' inclusione è rigorosa. Per le esigenze di tempo e spazio, la risposta a tali domande è data rispettivamente dai teoremi di gerarchia temporale e spaziale. Si chiamano teoremi gerarchici perchè inducono una corretta gerarchia sulle classi definite limitando le rispettive risorse. Così ci sono coppie di classi di complessità tali che una è adeguatamente inclusa nell' altra. Dopo aver dedotto tali inclusioni set corretto, possiamo procedere a fare dichiarazioni quantitative su quanto più tempo o spazio aggiuntivo è necessario per aumentare il numero di problemi che possono essere risolti.
Che tipo di dichiarazione viene fatta nel tentativo di stabilire i requisiti di tempo e spazio necessari per migliorare il numero definitivo di problemi risolti?
dichiarazioni quantitative