scientific article; zbMATH DE number 3988704
From MaRDI portal
Publication:3751001
zbMATH Open0611.68016MaRDI QIDQ3751001FDOQ3751001
Authors: Dung T. Huynh
Publication date: 1986
Title of this publication is not available (Why is that?)
Recommendations
randomnessChurch randomnessalmost everywhere hard languagesdescriptional complexity of Boolean circuits and formulasexponential- size circuits and formulasKolmogorov complexity of languagesKolmogorov-random languages
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)