scientific article; zbMATH DE number 3988704

zbMATH Open0611.68016MaRDI QIDQ3751001FDOQ3751001

Authors: Dung T. Huynh 

Publication date: 1986

Title of this publication is not available (Why is that?)

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

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)

Cited In (16)

• Kolmogorov complexity cores
• On solving hard problems by polynomial-size circuits
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Some Observations about the Randomness of Hard Problems
• Random languages for nonuniform complexity classes
• 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)