An excursion to the Kolmogorov random strings

DOI10.1006/JCSS.1997.1484zbMATH Open0882.68077OpenAlexW2109677942WikidataQ60578984 ScholiaQ60578984MaRDI QIDQ1362331FDOQ1362331

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

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

zbMATH Keywords

Kolmogorov random strings

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (13)

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

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)