An excursion to the Kolmogorov random strings

DOI10.1006/JCSS.1997.1484MaRDI QIDQ1362331zbMATH OpenOpenAlexWikidataFDO

Authors Harry Buhrman, Elvira Mayordomo

Publication date 3 August 1997

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/1323

zbMATH Keywords

Kolmogorov random strings

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Kolmogorov-Loveland stochasticity for finite strings
• On the complexity of random strings
• Random string: an explicitly solvable model
• Limitations of efficient reducibility to the Kolmogorov random strings
• Lower bounds for reducibility to the Kolmogorov random strings
• On the computational power of random strings
• Deviations from uniformity in random strings
• Generating Kolmogorov random strings from sources with limited independence
• Note on the topological structure of random strings
• scientific article; zbMATH DE number 7650389

Cites work

• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 107774 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261804 (Why is no real title available?)
• scientific article; zbMATH DE number 1555954 (Why is no real title available?)
• Almost everywhere high nonuniform complexity
• Classical recursion theory. Vol. II
• Completeness, the Recursion Theorem, and Effectively Simple Sets
• Cook versus Karp-Levin: Separating completeness notions if NP is not small
• Genericity and measure for exponential time (extended abstract)
• Instance complexity
• Localization of a theorem of Ambos-Spies and the strong anti-splitting property
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• On the complexity of random strings
• Polynomial-time reducibilities and ``almost all oracle sets
• Relative to a random oracle, NP is not small
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• The Complexity and Distribution of Hard Problems
• The complexity of theorem-proving procedures
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Weakly Hard Problems

Cited in

(13)

• What can be efficiently reduced to the Kolmogorov-random strings?
• Hard sets are hard to find
• Non-uniform reductions
• scientific article; zbMATH DE number 5023089 (Why is no real title available?)
• A stochastic string with a compound Poisson process
• Deviations from uniformity in random strings
• Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
• On the Topological Size of Sets of Random Strings
• Connections Between Bernoulli Strings and Random Permutations
• On the complexity of random strings
• Weak completeness notions for exponential time
• The Complexity of Complexity
• scientific article; zbMATH DE number 5864537 (Why is no real title available?)

This page was built for publication: An excursion to the Kolmogorov random strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1362331)