Feasible reductions to Kolmogorov-Loveland stochastic sequences
type: Item
instance of: scholarly article
title: Feasible reductions to Kolmogorov-Loveland stochastic sequences
zbMATH Open document ID: 0930.68068
DOI: 10.1016/S0304-3975(99)00041-9
author: Jack H. Lutz
author: David L. Schweizer
published in: Theoretical Computer Science
publication date: 2000-01-12T00:00:00Z
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 1387551
zbMATH Keywords: algorithmically random sequences
zbMATH Keywords: foundations of randomness
zbMATH Keywords: Kolmogorov-Loveland stochasticity
zbMATH Keywords: polynomial-time reductions
MaRDI profile type: Publication
cites work: Q3820592
cites work: On Languages Reducible to Algorithmically Random Languages
cites work: An observation on probability versus randomness with applications to complexity classes
cites work: Q4818850
cites work: Equivalence of Measures of Complexity Classes
cites work: A Theory of Program Size Formally Identical to Information Theory
cites work: Information, randomness and incompleteness. Papers on algorithmic information theory
cites work: Incompleteness theorems for random reals
cites work: Every sequence is reducible to a random one
cites work: A guided tour of Chernoff bounds
cites work: Computational depth and reducibility
cites work: Q5333652
cites work: Combinatorial foundations of information theory and the calculus of probabilities
cites work: Algorithms and Randomness
cites work: Q3758821
cites work: Q4070738
cites work: Q4023358
cites work: The Kleene Hierarchy Classification of Recursively Random Sequences
cites work: A New Interpretation of the von Mises' Concept of Random Sequence
cites work: Almost everywhere high nonuniform complexity
cites work: On independent random oracles
cites work: The definition of random sequences
cites work: A unified approach to the definition of random sequences
cites work: Process complexity and effective random tests
cites work: Q3969618
cites work: Q4733163
cites work: Synchronized rational relations of finite and infinite words
cites work: Can an individual sequence of zeros and ones be random?
cites work: Von Mises' definition of random sequences reconsidered
full work available at URL: s0304-3975(99)00041-9
OpenAlex ID: W2008350754
description: scientific article; zbMATH DE number 1387551