Closure of resource-bounded randomness notions under polynomial-time permutations

DOI10.4230/LIPICS.STACS.2018.51MaRDI QIDQ3304150zbMATH OpenFDO

Authors André Nies, Frank Stephan

Publication date 5 August 2020

Full work available at URL https://arxiv.org/abs/1709.08792

zbMATH Keywords

closure under permutationscomputational complexitymartingalesrandomness via resource-bounded betting strategies

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: An infinite bit sequence is called recursively random if no computable strategy betting along the sequence has unbounded capital. It is well-known that the property of recursive randomness is closed under computable permutations. We investigate analogous statements for randomness notions defined by betting strategies that are computable within resource bounds. Suppose that S is a polynomial time computable permutation of the set of strings over the unary alphabet (identified with N). If the inverse of S is not polynomially bounded, it is easy to build a polynomial time random bit sequence Z such that Z o S is not polynomial time random. So one should only consider permutations S satisfying the extra condition that the inverse is polynomially bounded. Now the closure depends on additional assumptions in complexity theory. Our first result shows that if BPP contains a superpolynomial deterministic time class then polynomial time randomness is not preserved by some permutation S such that in fact both S and its inverse are in P. Our second result shows that polynomial space randomness is preserved by polynomial time permutations with polynomially boun-ded inverse, so if P=PSPACE then polynomial time randomness is preserved.

Recommendations

• Resource bounded randomness and computational complexity
• scientific article; zbMATH DE number 969633
• Resource bounded randomness and weakly complete problems
• On the notion of infinite pseudorandom sequences
• Limits on the Computational Power of Random Strings

Cites work

• A Generalization of Resource-Bounded Measure, with Application to the BPP vs. EXP Problem
• Algorithmic randomness and complexity.
• Computability and randomness
• Feasible analysis, randomness, and base invariance
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 969633 (Why is no real title available?)
• scientific article; zbMATH DE number 6325425 (Why is no real title available?)
• Lowness properties and randomness
• Randomness and differentiability
• The axiomatization of randomness
• The definition of random sequences
• Using random sets as oracles
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(2)

• Certifying algorithms and relevant properties of reversible primitive permutations with \textsf{Lean}
• On Resource-Bounded Versions of the van Lambalgen Theorem

This page was built for publication: Closure of resource-bounded randomness notions under polynomial-time permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3304150)