Generic separations and leaf languages

DOI10.1002/MALQ.200310037MaRDI QIDQ4419264zbMATH OpenOpenAlexFDO

Authors Matthias Galota, Sven Kosub, Heribert Vollmer

Publication date 31 July 2003

Published in MLQ (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.200310037

zbMATH Keywords

Computational complexitygeneric oracleleaf languageoracle separationstructural complexitytype-2 complexity theory P-NP-problem

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Formal languages and automata (68Q45)

Recommendations

• A characterization of the leaf language classes
• Machines, Computations, and Universality
• Relating polynomial time to constant depth
• A uniform approach to define complexity classes
• Generic separations

Cited in

(4)

• Relating polynomial time to constant depth
• A characterization of the leaf language classes
• Mathematical Foundations of Computer Science 2005
• Machines, Computations, and Universality

This page was built for publication: Generic separations and leaf languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4419264)