Sets with small generalized Kolmogorov complexity
- 1 November 1986
- journal article
- research article
- Published by Springer Nature in Acta Informatica
- Vol. 23 (6) , 679-688
- https://doi.org/10.1007/bf00264313
Abstract
No abstract availableKeywords
This publication has 16 references indexed in Scilit:
- Sparse oracles, lowness, and highnessPublished by Springer Nature ,2006
- On sparse oracles separating feasible complexity classesPublished by Springer Nature ,1986
- Continuous optimization problems and a polynomial hierarchy of real functionsJournal of Complexity, 1985
- On Restricting the Size of Oracles Compared with Restricting Access to OraclesSIAM Journal on Computing, 1985
- On Circuit-Size Complexity and the Low Hierarchy in NPSIAM Journal on Computing, 1985
- On bounded query machinesTheoretical Computer Science, 1985
- Quantitative Relativizations of Complexity ClassesSIAM Journal on Computing, 1984
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975
- Information-Theoretic Limitations of Formal SystemsJournal of the ACM, 1974
- On the Length of Programs for Computing Finite Binary SequencesJournal of the ACM, 1966