The generalized Kolmogorov complexity of sets
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 186-194
- https://doi.org/10.1109/sct.1989.41824
Abstract
Recent work has shown that it is useful to consider new variants of time-bounded Kolmogorov complexity. The author reviews that work, presents the new definitions, and studies the basic properties of these measures. He deals with the function K/sub L/, which measures the complexity of the simplest strings in the language L and with sets of the form KU/sub v/(s(n),t(n)), which consists of strings with unique short descriptions.Keywords
This publication has 19 references indexed in Scilit:
- Limitations of the upward separation techniqueTheory of Computing Systems, 1991
- P-Printable SetsSIAM Journal on Computing, 1988
- On sparse oracles separating feasible complexity classesInformation Processing Letters, 1988
- On the notion of infinite pseudorandom sequencesTheoretical Computer Science, 1986
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Resource-bounded Kolmogorov complexity of hard languagesPublished by Springer Nature ,1986
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- Compression and rankingPublished by Association for Computing Machinery (ACM) ,1985
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- On sparse sets in NP–PInformation Processing Letters, 1983