Kolmogorov complexity and degrees of tally sets
From MaRDI portal
Publication:916650
DOI10.1016/0890-5401(90)90052-JzbMath0704.03023OpenAlexW2090493738MaRDI QIDQ916650
Osamu Watanabe, Eric W. Allender
Publication date: 1990
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(90)90052-j
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (5)
Degrees and reducibilities of easy tally sets ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Almost everywhere high nonuniform complexity ⋮ Reducibilities on tally and sparse sets ⋮ The structure of logarithmic advice complexity classes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
- Continuous optimization problems and a polynomial hierarchy of real functions
- A comparison of polynomial time reducibilities
- Computation times of NP sets of different densities
- Sets with small generalized Kolmogorov complexity
- Bi-immune sets for complexity classes
- Minimal degrees for polynomial reducibilities
- On Sets Truth-Table Reducible to Sparse Sets
- The Boolean Hierarchy I: Structural Properties
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- P-Printable Sets
This page was built for publication: Kolmogorov complexity and degrees of tally sets