An excursion to the Kolmogorov random strings
type: Item
instance of: scholarly article
title: An excursion to the Kolmogorov random strings
zbMATH Open document ID: 0882.68077
author: Harry Buhrman
author: Elvira Mayordomo
published in: Journal of Computer and System Sciences
publication date: 1997-08-03T00:00:00Z
full work available at URL: https://ir.cwi.nl/pub/1323
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1042926
zbMATH Keywords: Kolmogorov random strings
MaRDI profile type: Publication
OpenAlex ID: W2109677942
Wikidata QID: Q60578984
cites work: Localization of a theorem of Ambos-Spies and the strong anti-splitting property
cites work: Genericity and measure for exponential time
cites work: Q4525724
cites work: Q4039803
cites work: Q3996675
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: The complexity of theorem-proving procedures
cites work: Q4198056
cites work: The Complexity and Distribution of Hard Problems
cites work: Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
cites work: Relative to a random oracle, NP is not small
cites work: On the Complexity of Learning Minimum Time-Bounded Turing Machines
cites work: On the complexity of random strings
cites work: Q4071737
cites work: Q4023358
cites work: Almost everywhere high nonuniform complexity
cites work: Weakly Hard Problems
cites work: Cook versus Karp-Levin: Separating completeness notions if NP is not small
cites work: Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
cites work: Completeness, the Recursion Theorem, and Effectively Simple Sets
cites work: Classical recursion theory. Vol. II
cites work: Instance complexity
cites work: Q4231907
cites work: Polynomial-time reducibilities and ``almost all'' oracle sets
DOI: 10.1006/JCSS.1997.1484
Recommended article: Kolmogorov-Loveland stochasticity for finite strings
Recommended article: On the complexity of random strings
Recommended article: Random string: an explicitly solvable model
Recommended article: Limitations of Efficient Reducibility to the Kolmogorov Random Strings
Recommended article: Lower Bounds for Reducibility to the Kolmogorov Random Strings
Recommended article: On the computational power of random strings
Recommended article: Deviations from uniformity in random strings
Recommended article: Generating Kolmogorov random strings from sources with limited independence
Recommended article: Note on the topological structure of random strings
Recommended article: Q5875741
description: scientific article; zbMATH DE number 1042926