ISSN:
1436-5057
Keywords:
Complexity classes
;
honesty classes
;
honesty procedures
;
naming theorem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Description / Table of Contents:
Zusammenfassung Ein wichtiges Ergebnis der Komplexitätstheorie ist der Umbenennungssatz von E. M. McCreight, der besagt, daß es einen Algorithmus σ gibt, der alle Namen ϕi des Systems der Komplexitätsklassen in neue Namen ϕσ(i) überführt, derart, daß die neuen Namen die Schrittmaßbedingung „λi,n,m[ϕσ(i)(n)≦m] entscheidbar” erfüllen. Unsere Untersuchung der „gutartigen Funktionenklassen” zeigt, daß ein entsprechender Umbenennungsalgorithmus für diese Klassen nicht existiert.
Notes:
Abstract An important result in the theory of complexity classes is the naming theorem of E. M. McCreight, which states that the system of complexity classes can be renamed uniformly by a measured set of names. Our investigation of honesty classes shows that for these classes the analogous assertion is false. No measured transformation of programs renames correctly all honesty classes.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02242317
Permalink