Lexikon der Mathematik: Hierarchiesatz
für einen Ressourcentyp die Aussage, daß eine geringe Erhöhung der Ressourcen die Menge der lösbaren Probleme echt vergrößert.
Der deterministische Zeithierarchiesatz für Turing-Maschinen besagt unter schwachen Annahmen an die Funktionen T1 und T2, daß, falls
Es wird vermutet, daß Hierarchiesätze für die Komplexitätsklassen der polynomiellen Hierarchie sowie für die Sprachklassen ACk, ACCk, non-uniform-NCk und TCk (und wachsendes k) gelten.
Schreiben Sie uns!