Computational depth: Concept and applications

DOI10.1016/j.tcs.2005.11.033zbMath1088.68073OpenAlexW2072053479MaRDI QIDQ2368976

N. V. Vinodchandran, Dieter van Melkebeek, Luís Antunes, Lance J. Fortnow

Publication date: 28 April 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.11.033

zbMATH Keywords

Kolmogorov complexityStructural complexity and average case complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (19)

Sophistication revisited ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Lowness and logical depth ⋮ Depth, Highness and DNR Degrees ⋮ Pushdown and Lempel-Ziv depth ⋮ Kolmogorov's Last Discovery? (Kolmogorov and Algorithmic Statistics) ⋮ Algorithmic Statistics: Forty Years Later ⋮ Low-depth witnesses are easy to find ⋮ On the Difference Between Finite-State and Pushdown Depth ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ On the Polynomial Depth of Various Sets of Random Strings ⋮ Sophistication vs logical depth ⋮ Information measures for infinite sequences ⋮ Time-bounded incompressibility of compressible strings and sequences ⋮ Searching for shortest and least programs ⋮ Depth as randomness deficiency ⋮ Algorithmic Statistics Revisited ⋮ Polylog depth, highness and lowness for E ⋮ Two Problems for Sophistication

Cites Work

• On the theory of average case complexity
• Average case complexity under the universal distribution equals worst- case complexity
• Hardness vs randomness
• On resource-bounded instance complexity
• Average Case Complete Problems
• Randomness conservation inequalities; information and independence in mathematical theories
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• The Complexity of Malign Measures
• Resource-bounded kolmogorov complexity revisited
• Fundamentals of Computation Theory
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computational depth: Concept and applications