Feasible reductions to Kolmogorov-Loveland stochastic sequences
From MaRDI portal
Publication:1960665
DOI10.1016/S0304-3975(99)00041-9zbMath0930.68068OpenAlexW2008350754MaRDI QIDQ1960665
Jack H. Lutz, David L. Schweizer
Publication date: 12 January 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00041-9
polynomial-time reductionsKolmogorov-Loveland stochasticityalgorithmically random sequencesfoundations of randomness
Related Items (2)
The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences ⋮ Kolmogorov-Loveland randomness and stochasticity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Synchronized rational relations of finite and infinite words
- A guided tour of Chernoff bounds
- Incompleteness theorems for random reals
- On independent random oracles
- Almost everywhere high nonuniform complexity
- Computational depth and reducibility
- Process complexity and effective random tests
- Can an individual sequence of zeros and ones be random?
- Combinatorial foundations of information theory and the calculus of probabilities
- Every sequence is reducible to a random one
- Von Mises' definition of random sequences reconsidered
- Algorithms and Randomness
- A Theory of Program Size Formally Identical to Information Theory
- Equivalence of Measures of Complexity Classes
- An observation on probability versus randomness with applications to complexity classes
- On Languages Reducible to Algorithmically Random Languages
- A New Interpretation of the von Mises' Concept of Random Sequence
- The Kleene Hierarchy Classification of Recursively Random Sequences
- A unified approach to the definition of random sequences
- The definition of random sequences
This page was built for publication: Feasible reductions to Kolmogorov-Loveland stochastic sequences
