IEEE - Institute of Electrical and Electronics Engineers, Inc. - Generalized Kolmogorov complexity and the structure of feasible computations

24th Annual Symposium on Foundations of Computer Science (sfcs 1983)

Author(s): Hartmanis, Juris
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 November 1983
Conference Location: Tucson, AZ, USA, USA
Conference Date: 7 November 1983
Page(s): 439 - 445
ISBN (Paper): 0-8186-0508-1
ISSN (Paper): 0272-5428
DOI: 10.1109/SFCS.1983.21
Regular:

In this paper we define a generalized, two-parameter, Kolmogorov complexity of finite strings which measures how much and how fast a string can be compressed and we show that this string... View More

Advertisement