scientific article; zbMATH DE number 3988704

MaRDI QIDQ3751001zbMATH OpenFDO

Authors Dung T. Huynh

Publication date 1986

zbMATH Keywords

randomnessChurch randomnessalmost everywhere hard languagesdescriptional complexity of Boolean circuits and formulasexponential- size circuits and formulasKolmogorov complexity of languagesKolmogorov-random languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On Languages with Very High Space-Bounded Kolmogorov Complexity
• Randomness is hard
• scientific article; zbMATH DE number 107775
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• scientific article; zbMATH DE number 1335898

Cited in

(16)

• Kolmogorov complexity cores
• On solving hard problems by polynomial-size circuits
• scientific article; zbMATH DE number 107775 (Why is no real title available?)
• Nonuniform complexity and the randomness of certain complete languages
• Resource bounded randomness and computational complexity
• Refined Bounds on Kolmogorov Complexity for ω-Languages
• Almost everywhere high nonuniform complexity
• Circuit size relative to pseudorandom oracles
• Effective entropies and data compression
• Random languages for nonuniform complexity classes
• Some Observations about the Randomness of Hard Problems
• scientific article; zbMATH DE number 4187790 (Why is no real title available?)
• Curiouser and curiouser: the link between incompressibility and complexity
• On Languages with Very High Space-Bounded Kolmogorov Complexity
• An upward measure separation theorem
• On problems for which no oracle can help

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)