Polylog depth, highness and lowness for E

DOI10.1016/j.ic.2019.104483zbMath1441.68112arXiv1602.03332OpenAlexW2980716298WikidataQ127016601 ScholiaQ127016601MaRDI QIDQ2304528

Philippe Moser

Publication date: 12 March 2020

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1602.03332

zbMATH Keywords

algorithmic information theoryKolmogorov complexityBennett logical depth

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Pushdown and Lempel-Ziv depth ⋮ On the Difference Between Finite-State and Pushdown Depth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Almost everywhere high nonuniform complexity
• Lowness and logical depth
• On the polynomial depth of various sets of random strings
• Computational depth: Concept and applications
• A zero-one law for RP and derandomization of AM if NP is not small
• Dimension, entropy rates, and compression
• Algorithmic Randomness and Complexity
• Lowness Properties of Sets in the Exponential-Time Hierarchy
• Feasible Depth
• Power from Random Strings

This page was built for publication: Polylog depth, highness and lowness for E