Hierarchiesätze

Einfache Sprache

Intuitiv geht es hier darum das mit mehr Ressourcen, Zeit oder Raum, mehr Probleme gelöst werden können.

Def. Hierarchiesätze

Die Hierarchiesätze umfassen mehrere Sätze die zeigen das es innerhalb von Komplexitätsklasse eine Hierarchie (Rangordnung) bzgl. wie viele Sprachen sie enthalten. So z.B. in $O(n^3)$ mehr Sprachen entscheidbar sind als in $O(n^2)$.

• Raumhierarchiesatz
• Zeithierarchiesatz