Kolmogorov Complexity and Computational Complexity

By Osamu Watanabe. 2012

63 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. J. Urgen Schmidhuber
2. Yoshua Bengio
3. N. Schraudolph
4. Mohit Bansal
5. Jieyu Zhao
6. Ruslan Salakhutdinov
7. Quoc V. Le
8. Alexandre V. Borovik

In Computational Theory and Mathematics

1. J. Urgen Schmidhuber
2. N. Schraudolph
3. Alexandre V. Borovik
4. Vladimir Shpilrain
5. Marco A. Wiering
6. Jieyu Zhao
7. Alexei G. Myasnikov
8. Hado van Hasselt

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].”
• Measuring sets in infinite groups (2002, methodology): “We refer to [12], [22] for detailed treatment of Kolmogorov complexity.”
• Reinforcement Learning with Self-Modifying Policies (1998, background): “Despite this strong result, until recently LS has not received much attention except in purely theoretical studies | see, e.g., [14].”
• Simple Principles of Metalearning (1996, background): “Still, until recently LS has not received much attention except in purely theoretical studies | see, e.g., (Watanabe, 1992).”