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