Benutzer: Gast  Login
Dokumenttyp:
Technical Report 
Autor(en):
Matthias Galota; Sven Kosub; Heribert Vollmer 
Titel:
Generic Separations and Leaf Languages 
Abstract:
In the early nineties of the previous century, leaf languages were introduced as a means for the uniform characterization of many complexity classes, mainly in the range between P (polynomial time) and PSPACE (polynomial space). It was shown that the separability of two complexity classes can be reduced to a combinatorial property of the corresponding defining leaf languages. In the present paper, it is shown that every separation obtained in this way holds for every generic oracle in the sense...    »
 
Stichworte:
computational and structural complexity; leaf language; oracle separation; generic oracle; type-2 complexity theory 
Jahr:
2001 
Jahr / Monat:
2001-09-01 00:00:00