An excursion to the Kolmogorov random strings
From MaRDI portal
Publication:1362331
DOI10.1006/jcss.1997.1484zbMath0882.68077OpenAlexW2109677942WikidataQ60578984 ScholiaQ60578984MaRDI QIDQ1362331
Elvira Mayordomo, Harry Buhrman
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
Related Items (5)
The Complexity of Complexity ⋮ Non-uniform reductions ⋮ Hard sets are hard to find ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Weak completeness notions for exponential time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Cook versus Karp-Levin: Separating completeness notions if NP is not small
- Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
- Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
- Almost everywhere high nonuniform complexity
- Classical recursion theory. Vol. II
- Relative to a random oracle, NP is not small
- Polynomial-time reducibilities and ``almost all oracle sets
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- Localization of a theorem of Ambos-Spies and the strong anti-splitting property
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Instance complexity
- On the complexity of random strings
- The Complexity and Distribution of Hard Problems
- Weakly Hard Problems
- Genericity and measure for exponential time
- Completeness, the Recursion Theorem, and Effectively Simple Sets
- The complexity of theorem-proving procedures
This page was built for publication: An excursion to the Kolmogorov random strings
