Journal of the ACM Bibliography
Pekka Orponen, Ker-I Ko, Uwe Schöning, and Osamu Watanabe. Instance
complexity. Journal of the ACM, 41(1):96-121, January 1994.
[BibTeX entry]
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.
Shortcuts: