Applications of Time-Bounded Kolmogorov Complexity in Complexity Theory

By Eric Allender. 1992

Citations in the corpus

• Deep learning in neural networks: An overview (2014, background): “Somemethods explicitly take into account program runtime (Allender, 1992; Schmidhuber, 1997, 2002; Watanabe, 1992); many consider only programs with constant runtime, written in non-universal programming languages (e.g., Hinton & van Camp, 1993; Rissanen, 1986).”
• On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, background): “of Kolmogorov complexity that explicitly take into account program runtime [146, 6, 291, 147, 235, 237].”
• An Introduction to Kolmogorov Complexity and Its Applications (1993, unknown): “[10] Show that there exists a constant c such that c(onln):::; c for all n, and c(on) 2:: logn - c for infinitely many n.”