Dimension Characterizations of Complexity Classes

DOI10.1007/11821069_41MaRDI QIDQ5756668zbMATH OpenOpenAlexFDO

Authors Xiaoyang Gu, Jack H. Lutz

Publication date 5 September 2007

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11821069_41

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Dimension characterizations of complexity classes
• Dimension and the structure of complexity classes
• Dimension in Complexity Classes
• Kolmogorov characterizations of complexity classes
• Quantitative Relativizations of Complexity Classes
• scientific article; zbMATH DE number 3885883
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions
• Qualitative relativizations of complexity classes
• Logical and schematic characterization of complexity classes
• Complexity classes as mathematical axioms

Cited in

(7)

• Characterization of realizable space complexities
• Pushdown dimension
• The complexity of the classification problems of finite-dimensional continua
• Dimension characterizations of complexity classes
• Dimension extractors and optimal decompression
• scientific article; zbMATH DE number 4213458 (Why is no real title available?)
• Complexity of computing Vapnik-Chervonenkis dimension and some generalized dimensions

This page was built for publication: Dimension Characterizations of Complexity Classes

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