A note on dimensions of polynomial size circuits
From MaRDI portal
Publication:2503295
DOI10.1016/j.tcs.2006.02.022zbMath1099.68045MaRDI QIDQ2503295
Publication date: 14 September 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2006.02.022
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Effective dimensions and relative frequencies, Pushdown dimension, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Effective Dimensions and Relative Frequencies
Cites Work
- Unnamed Item
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
- Almost everywhere high nonuniform complexity
- A sequence of complexly computable functions
- Resource bounded randomness and weakly complete problems
- Scaled dimension and nonuniform complexity
- The dimensions of individual strings and sequences
- Dimension, entropy rates, and compression
- Circuit-size lower bounds and non-reducibility to sparse sets
- Cosmological lower bound on the circuit complexity of a small problem in logic
- Category and Measure in Complexity Classes
- Two definitions of fractional dimension
- Dimension in Complexity Classes
- STACS 2004