Kolmogorov complexity and degrees of tally sets

DOI10.1016/0890-5401(90)90052-JzbMATH Open0704.03023OpenAlexW2090493738MaRDI QIDQ916650FDOQ916650

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

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

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)

Cites Work

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

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)