Resource-bounded Kolmogorov complexity of hard languages
- 1 January 1986
- book chapter
- Published by Springer Nature
- p. 184-195
- https://doi.org/10.1007/3-540-16486-3_97
Abstract
No abstract availableKeywords
This publication has 24 references indexed in Scilit:
- Generalized Kolmogorov complexity and the structure of feasible computationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Circuit-size lower bounds and non-reducibility to sparse setsInformation and Control, 1982
- Some connections between nonuniform and uniform complexity classesPublished by Association for Computing Machinery (ACM) ,1980
- Two theorems on random polynomial timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977
- On the structure of complete sets: Almost everywhere complexity and infinitely often speedupPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- The circuit value problem is log space complete for PACM SIGACT News, 1975
- Random Sets in Subrecursive HierarchiesJournal of the ACM, 1969
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966
- On the concept of a random sequenceBulletin of the American Mathematical Society, 1940