Premium
Generic separations and leaf languages
Author(s) -
Galota Matthias,
Kosub Sven,
Vollmer Heribert
Publication year - 2003
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200310037
Subject(s) - oracle , pspace , mathematics , characterization (materials science) , property (philosophy) , time complexity , complexity class , range (aeronautics) , space (punctuation) , polynomial , discrete mathematics , combinatorics , computational complexity theory , computer science , algorithm , programming language , mathematical analysis , philosophy , materials science , epistemology , composite material , nanotechnology , operating system
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 of Blum and Impagliazzo. We obtain several consequences of this result, regarding, e. g., universal oracles, simultaneous separations and type‐2 complexity.