Kolmogorov complexity and degrees of tally sets

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

zbMATH Keywords

polynomial timeexponential timetally setgeneralized Kolmogorov complexityNE predicate

Mathematics Subject Classification ID

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