scientific article; zbMATH DE number 3988704

From MaRDI portal
Publication:3751001





[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.











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)