Dimension characterizations of complexity classes

DOI10.1007/S00037-008-0257-XzbMATH Open1185.68344OpenAlexW2099020009MaRDI QIDQ2269007FDOQ2269007

Authors: Xiaoyang Gu, Jack H. Lutz 

Publication date: 15 March 2010

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-008-0257-x

Recommendations

• Dimension Characterizations of Complexity Classes
• A Pseudorandom Oracle Characterization of ${\text{BPP}}$
• scientific article; zbMATH DE number 3995648
• An observation on probability versus randomness with applications to complexity classes
• On the robustness of ALMOST-$\mathcal {R}$

zbMATH Keywords

derandomization

Mathematics Subject Classification ID

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

Cited In (5)

• Characterization of realizable space complexities
• The complexity of the classification problems of finite-dimensional continua
• Title not available (Why is that?)
• Dimension Characterizations of Complexity Classes
• 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 Q2269007)