I teoremi di gerarchia temporale e spaziale costituiscono la base per la maggior parte dei risultati di separazione delle classi di complessità. Per esempio, il teorema della gerarchia temporale ci dice che P è strettamente contenuto in EXPTIME, e il teorema della gerarchia spaziale ci dice che L è strettamente contenuto in PSPACE.
All' interno di quale variabile L è vincolata secondo il teorema della gerarchia spaziale?
PSPACE PSPACE PSPACE