Journal of the ACM Bibliography
Gregory J. Chaitin. A theory
of program size formally identical to information theory. Journal
of the ACM, 22(3):329-340, July 1975.
[BibTeX entry]
Selected papers that cite this one
- Ronald V. Book, Jack H. Lutz, and David M. Martin Jr. The global power of additional queries
to random oracles. Information and Computation,
120(1):49-54, July 1995.
- Ronald V. Book and Osamu Watanabe. On random hard sets for NP.
Information and Computation, 125(1):70-76, 25 February
1996.
- Gregory J. Chaitin. Information-theoretic
characterizations of recursive infinite strings. Theoretical
Computer Science, 2(1):45-48, June 1976.
- Martin Dowd. Generic oracles,
uniform machines, and codes. Information and
Computation, 96(1):65-76, January 1992.
- Steven M. Kautz and Peter Bro Miltersen. Relative to a random
oracle, NP is not small. Journal of Computer and System
Sciences, 53(2):235-250, October 1996.
- Ming Li and Paul M. B. Vitányi. Statistical properties of
finite sequences with high Kolmogorov complexity. Mathematical
Systems Theory, 27(4):365-376, July/August 1994.
- Aaron Shenhar. On the Kolmogorov
complexity of arbitrary objects. Journal of Complexity,
9(4):499-517, December 1993.
- Ray J. Solomonoff. The discovery of
algorithmic probability. Journal of Computer and System
Sciences, 55(1):73-88, August 1997.
- V. A. Uspensky and A. Shen. Relations between
varieties of Kolmogorov complexities. Mathematical Systems
Theory, 29(3):271-292, May/June 1996.
- V. G. Vovk. Universal
forecasting algorithms. Information and Computation,
96(2):245-277, February 1992.
Shortcuts: