Generalized Kolmogorov complexity and the structure of feasible computations
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 439-445
- https://doi.org/10.1109/sfcs.1983.21
Abstract
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 complexity measure is an efficient tool for the study of computational complexity. The advantage of this approach is that it not only classifies strings as random or not random, but measures the amount of randomness detectable in a given time. This permits the study how computations change the amount of randomness of finite strings and thus establish a direct link between computational complexity and generalized Kolmogorov complexity of strings. This approach gives a new viewpoint for computational complexity theory, yields natural formulations of new problems and yields new results about the structure of feasible computations.Keywords
This publication has 17 references indexed in Scilit:
- Sparse sets in NP-P: EXPTIME versus NEXPTIMEInformation and Control, 1985
- Oracle-dependent properties of the lattice of NP setsTheoretical Computer Science, 1983
- On sparse sets in NP–PInformation Processing Letters, 1983
- A complexity theoretic approach to randomnessPublished by Association for Computing Machinery (ACM) ,1983
- A Fast Monte-Carlo Test for PrimalitySIAM Journal on Computing, 1977
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ QuestionSIAM Journal on Computing, 1975
- Information-Theoretic Limitations of Formal SystemsJournal of the ACM, 1974
- Reducibility among Combinatorial ProblemsPublished by Springer Nature ,1972
- The complexity of theorem-proving proceduresPublished by Association for Computing Machinery (ACM) ,1971
- Two-Tape Simulation of Multitape Turing MachinesJournal of the ACM, 1966