Kolmogorov complexity and degrees of tally sets
- 1 June 1990
- journal article
- Published by Elsevier in Information and Computation
- Vol. 86 (2) , 160-178
- https://doi.org/10.1016/0890-5401(90)90052-j
Abstract
No abstract availableKeywords
This publication has 13 references indexed in Scilit:
- Some consequences of the existence of pseudorandom generatorsJournal of Computer and System Sciences, 1989
- The Boolean Hierarchy I: Structural PropertiesSIAM Journal on Computing, 1988
- P-Printable SetsSIAM Journal on Computing, 1988
- On Sets Truth-Table Reducible to Sparse SetsSIAM Journal on Computing, 1988
- Minimal degrees for polynomial reducibilitiesJournal of the ACM, 1987
- Sets with small generalized Kolmogorov complexityActa Informatica, 1986
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NPTheoretical Computer Science, 1985
- Bi-immune sets for complexity classesTheory of Computing Systems, 1985
- Computation times of NP sets of different densitiesTheoretical Computer Science, 1984
- On Isomorphisms and Density of $NP$ and Other Complete SetsSIAM Journal on Computing, 1977