Selected papers that cite this one
- V. Arvind, J. Köbler, and M. Mundhenk. Upper bounds for the complexity of sparse and tally descriptions. Mathematical Systems Theory, 29(1):63-94, January/February 1996.
- José L. Balcázar and Montserrat Hermo. The structure of logarithmic advice complexity classes. Theoretical Computer Science, 207(1):217-244, 28 October 1998.
- Harry Buhrman and Elvira Mayordomo. An excursion to the Kolmogorov random strings. Journal of Computer and System Sciences, 54(3):393-399, June 1997.
- Harry Buhrman and Pekka Orponen. Random strings make hard instances. Journal of Computer and System Sciences, 53(2):261-266, October 1996.
- Lance Fortnow and Martin Kummer. On resource-bounded instance complexity. Theoretical Computer Science, 161(1-2):123-140, 15 July 1996.
- Lance Fortnow and Sophie Laplante. Nearly optimal language compression using extractors. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 84-93, Paris France, 25-27 February 1998. Springer.
- Martin Kummer. Kolmogorov complexity and instance complexity of recursively enumerable sets. SIAM Journal on Computing, 25(6):1123-1143, December 1996.
Selected references
- Ronald V. Book. Tally languages and complexity classes. Information and Control, 26(2):186-193, October 1974.
- Shimon Even, Alan L. Selman, and Yacov Yacobi. Hard-core theorems for complexity classes. Journal of the ACM, 32(1):205-217, January 1985.
- Juris Hartmanis. Generalized Kolmogorov complexity and the structure of feasible computations (preliminary report). In 24th Annual Symposium on Foundations of Computer Science, pages 439-445, Tucson, Arizona, 7-9 November 1983. IEEE.
- Richard M. Karp and Richard J. Lipton. Some connections between nonuniform and uniform complexity classes. In Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, pages 302-309, Los Angeles, California, 28-30 April 1980.
- D. W. Loveland. A variant of the Kolmogorov concept of complexity. Information and Control, 15(6):510-526, December 1969.
- Nancy Lynch. On reducibility to complex or sparse sets. Journal of the ACM, 22(3):341-345, July 1975.
- Pekka Orponen and Uwe Schöning. The density and complexity of polynomial cores for intractable. Information and Control, 70(1):54-68, July 1986.
- Michael Sipser. A complexity theoretic approach to randomness. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 330-335, Boston, Massachusetts, 25-27 April 1983.
- Robert E. Wilber. Randomness and the density of hard problems. In 24th Annual Symposium on Foundations of Computer Science, pages 335-342, Tucson, Arizona, 7-9 November 1983. IEEE.