Kolmogorov complexity and degrees of tally sets

DOI10.1016/0890-5401(90)90052-JMaRDI QIDQ916650zbMATH OpenOpenAlexFDO

Authors Osamu Watanabe, Eric 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

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Fast-Growing Functions and the P vs. NP Question
• scientific article; zbMATH DE number 3958736
• scientific article; zbMATH DE number 4213433
• scientific article; zbMATH DE number 3974293
• scientific article; zbMATH DE number 4045156
• Enumerations of the Kolmogorov function
• scientific article; zbMATH DE number 4208066
• scientific article; zbMATH DE number 3581615
• Towards separating nondeterminism from determinism
• scientific article; zbMATH DE number 2102763

Cites work

• scientific article; zbMATH DE number 3978383 (Why is no real title available?)
• scientific article; zbMATH DE number 4075037 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• Bi-immune sets for complexity classes
• Computation times of NP sets of different densities
• Continuous optimization problems and a polynomial hierarchy of real functions
• Minimal degrees for polynomial reducibilities
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Sets Truth-Table Reducible to Sparse Sets
• P-Printable Sets
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• Sets with small generalized Kolmogorov complexity
• Some remarks on witness functions for nonpolynomial and noncomplete sets in NP
• The Boolean Hierarchy I: Structural Properties

Cited in

(6)

• Degrees and reducibilities of easy tally sets
• The structure of logarithmic advice complexity classes
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• Kolmogorov complexity arguments in combinatorics
• Almost everywhere high nonuniform complexity
• Reducibilities on tally and sparse sets

This page was built for publication: Kolmogorov complexity and degrees of tally sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q916650)