Almost everywhere high nonuniform complexity
- 1 April 1992
- journal article
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 44 (2) , 220-258
- https://doi.org/10.1016/0022-0000(92)90020-j
Abstract
No abstract availableKeywords
This publication has 28 references indexed in Scilit:
- Kolmogorov Complexity, Complexity Cores, and the Distribution of HardnessPublished by Springer Nature ,1992
- Kolmogorov complexity and degrees of tally setsInformation and Computation, 1990
- Some consequences of the existence of pseudorandom generatorsJournal of Computer and System Sciences, 1989
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Some Observations about the Randomness of Hard ProblemsSIAM Journal on Computing, 1986
- How to construct random functionsJournal of the ACM, 1986
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Families of recursive predicates of measure zeroJournal of Mathematical Sciences, 1976
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966