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.
Qual è la base per i risultati della separazione all' interno delle classi di complessità?
teoremi di gerarchia temporale e spaziale teoremi di gerarchia temporale e spaziale