Benutzer: Gast  Login
Titel:

Generic Separations and Leaf Languages

Dokumenttyp:
Technical Report
Autor(en):
Matthias Galota; Sven Kosub; Heribert Vollmer
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
 BibTeX