scientific article; zbMATH DE number 3988704
[For the entire collection see Zbl 0591.00015.] This paper explores further the relationship between randomness and complexity. The concept of time-/space-bounded Kolmogorov complexity of languages is introduced. Among others we show that there exists a language L in \(DTIME(2^{2^{lin}})\) such that the \(2^{poly}\)-time- bounded Kolmogorov complexity of L is exponential almost everywhere. We study time-/space-bounded Kolmogorov complexity of languages that are \(DTIME(2^{2^{lin}})\)- \((SPACE(2^{lin})\)-) hard under polynomial- time Turing reductions. The connection between Kolmogorov-random languages and almost everywhere hard languages is investigated. We also show that Kolmogorov randomness implies Church randomness. Finally, we work out the relationship between time-/space-bounded Kolmogorov complexity and time-/space-bounded descriptional complexity of Boolean circuits and formulas for hard languages. This result provides a classification of exponential-size circuits and formulas in terms of the amount of information contained in them.
- On solving hard problems by polynomial-size circuits
- Random languages for nonuniform complexity classes
- Nonuniform complexity and the randomness of certain complete languages
- Almost everywhere high nonuniform complexity
- Circuit size relative to pseudorandom oracles
- Resource bounded randomness and computational complexity
- Curiouser and curiouser: the link between incompressibility and complexity
- scientific article; zbMATH DE number 4208066 (Why is no real title available?)
- Kolmogorov complexity cores
- Some Observations about the Randomness of Hard Problems
- On problems for which no oracle can help
- Kolmogorov complexity and computational complexity
- On Languages with Very High Space-Bounded Kolmogorov Complexity
- Refined Bounds on Kolmogorov Complexity for ω-Languages
- scientific article; zbMATH DE number 4187790 (Why is no real title available?)
- Effective entropies and data compression
- An upward measure separation theorem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3751001)