An excursion to the Kolmogorov random strings
From MaRDI portal
Publication:1362331
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
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)